A method for massively scalable phylogenetic network inference

Deze paper introduceert InPhyNet, een schaalbare methode die nauwkeurige fylogenetische netwerken kan afleiden voor duizenden taxa door het samenvoegen van onafhankelijke netwerken, waardoor zowel de beperkingen van bestaande modelgebaseerde methoden als de interpretatieproblemen van impliciete methoden worden overwonnen.

De kern

InPhyNet: De "Puzzelmeester" voor de Evolutie van Planten

Stel je voor dat je de geschiedenis van het leven op aarde wilt reconstrueren. Vroeger dachten wetenschappers dat dit een simpele stamboom was: een boom met een stam en takken die zich steeds in tweeën splitsen. Een ouder wordt twee kinderen, en zo gaat het door.

Maar de werkelijkheid is vaak rommeliger. Soms "trappen" twee verschillende takken van de boom in elkaar, of wisselen ze stukjes DNA uit. Denk aan hybridisatie (waar twee soorten planten kruisen) of horizontale gen-overdracht (waar bacteriën of planten DNA van een ander soort "lenen" in plaats van van hun ouders). In plaats van een boom, lijkt de geschiedenis meer op een web of een netwerk met kruisende lijnen.

Het probleem? Het reconstrueren van zo'n web is extreem moeilijk, vooral als je duizenden soorten tegelijk wilt analyseren. Bestaande methoden werken als een olifant in een porseleinkast: ze zijn nauwkeurig, maar ze kunnen maar heel weinig soorten tegelijk aan (maximaal 30 of 80). Als je duizenden soorten probeert te analyseren, duurt het berekenen eeuwen.

De oplossing: InPhyNet
De auteurs van dit paper (Kolbow, Kong en Solís-Lemus) hebben een nieuwe methode bedacht genaamd InPhyNet. Ze noemen het een "massief schaalbare" methode. Laten we het uitleggen met een paar analogieën:

1. De "Divide-and-Conquer" Strategie (De Grote Puzzel)

Stel je voor dat je een enorme puzzel van 1.000 stukjes moet maken, maar je hersenen kunnen er maar 20 tegelijk verwerken.

• De oude manier: Je probeert de hele puzzel in één keer te doen. Je hersenen gaan op hol, het duurt eeuwen en je geeft het op.
• De InPhyNet-methode: Je deelt de puzzel op in kleine, overzichtelijke stapels van 20 stukjes.
  1. Je lost elke kleine stapel apart op (je maakt kleine, perfecte mini-puzzels).
  2. Je gebruikt een slimme "lijm" (de InPhyNet-algoritme) om deze kleine puzzels weer aan elkaar te plakken tot één grote, complete puzzel.

Dit is wat ze Divide-and-Conquer (verdelen en overheersen) noemen. Het maakt het mogelijk om duizenden soorten te analyseren in plaats van slechts een handvol.

2. De "Kleefkracht" van de Netwerken

Hoe plakken ze de stukken aan elkaar zonder dat het mislukt?
Stel je voor dat elke kleine mini-puzzel een stempel heeft. InPhyNet kijkt naar deze stempels en naar een lijst met afstanden tussen de soorten (hoe ver ze van elkaar verwijderd zijn in de evolutie).

• Het algoritme zoekt naar de twee stukken die het beste bij elkaar passen.
• Het plakt ze samen.
• Het magische deel: Als twee stukken in een mini-puzzel een "kruising" hadden (een hybride), onthoudt InPhyNet dit. Later, als hij de grote puzzel bouwt, zorgt hij ervoor dat die kruisingen op de juiste plek in het grote web verschijnen, in plaats van ze te negeren.

3. De Test: De "Planten-Encyclopedie"

Om te bewijzen dat hun methode werkt, hebben ze het getest op een echte, gigantische dataset: 1.158 soorten landplanten (van de "One Thousand Plant Transcriptomes Initiative").

• Het resultaat: Ze konden een netwerk maken dat duizenden soorten omvatte.
• De ontdekking: Ze vonden plekken in de plantenfamilieboom waar de wetenschap het al lang niet eens was.
  • Voorbeeld: De Gnetales (een groep naaktzadigen) zijn een mysterie. Zijn ze familie van de dennen? Of van de cipressen? InPhyNet suggereert dat het misschien allebei is! Het netwerk toont een kruising die beide theorieën deelt.
  • Ze vonden ook bewijs voor kruisingen binnen de varenfamilie en de denfamilie, wat verklaart waarom sommige planten zo raar lijken.

Waarom is dit belangrijk?

Vroeger moesten we kiezen: of we kijken naar een simpele boom (en negeren we de rommelige kruisingen), of we kijken naar een complex web (maar dan alleen voor een paar soorten).
InPhyNet is als een super-snelheidslens. Het stelt ons in staat om de hele "web van het leven" te zien, inclusief alle kruisingen en verwarring, in een tijdsbestek dat haalbaar is.

Kortom:
InPhyNet is een slimme, snelle manier om de ingewikkelde, netvormige geschiedenis van het leven te tekenen, zelfs als je duizenden soorten tegelijk wilt bekijken. Het lost het probleem op dat we eerder vastzaten in de "olifant in de porseleinkast" en maakt nu de weg vrij om de echte, rommelige maar fascinerende geschiedenis van de evolutie te begrijpen.

Technische samenvatting

Titel: Een methode voor massief schaalbare inferentie van fylogenetische netwerken

Auteurs: Nathan Kolbow, SungsiK Kong, en Claudia Solís-Lemus.

---

1. Het Probleem

Recente vooruitgangen in sequencing-technologieën hebben grote hoeveelheden genomische data beschikbaar gemaakt voor fylogenetische analyses. Hoewel deze analyses vaak vertrouwen op fylogenetische bomen (die aannemen dat evolutie strikt bifurcerend is), is er steeds meer bewijs dat niet-boomachtige evolutionaire gebeurtenissen, zoals hybridisatie en horizontale genoverdracht, veel voorkomen.

• Beperking van bestaande methoden: Fylogenetische netwerken kunnen deze complexe geschiedenissen modelleren, maar bestaande inferentiemethoden (zoals SNaQ, PhyloNet-MPL, PhyNEST) zijn computationeel zeer intensief. Ze hebben een runtime-complexiteit van een hoogwaardig polynoom en kunnen momenteel slechts ongeveer 30 tot 81 taxa verwerken.
• Beperking van impliciete netwerken: Snellere methoden zoals NeighborNet genereren "impliciete" netwerken die conflicterende signalen samenvatten, maar missen biologische interpretatie en zijn niet gebaseerd op een coalescent-model.
• Behoefte: Er is een methode nodig die zowel schaalbaar is (voor honderden tot duizenden taxa) als biologisch accuraat (onder het multispecies network coalescent model).

2. Methodologie: InPhyNet

De auteurs introduceren InPhyNet, een nieuw algoritme dat gebruikmaakt van een "divide-and-conquer" (verdel-en-heersen) strategie om netwerken te construeren die lineair schalen met het aantal taxa.

Het raamwerk bestaat uit vier stappen:

1. Decompositie: De set van taxa $X$ wordt opgesplitst in disjuncte (niet-overlappende) subsets $S = \{S_i\}$.
2. Subnetwerk-inferentie: Voor elke subset $S_i$ wordt een level-1 netwerk ($C_i$) onafhankelijk afgeleid met bestaande, nauwkeurige methoden (zoals SNaQ of PhyloNet). Omdat de subsets klein zijn, zijn deze berekeningen haalbaar.
3. Dissimilariteitsmatrix: Een paarsgewijze dissimilariteitsmatrix $D$ wordt berekend voor alle taxa in $X$ (gebaseerd op de gemiddelde internode-afstand tussen genenbomen, AGID).
4. Merging (InPhyNet-algoritme): De kerninnovatie is het samenvoegen van de level-1 netwerken $C$ en de matrix $D$ tot één groot, semi-gericht netwerk $\hat{N}$.
   • Het algoritme start met een onvolledig netwerk met alleen bladeren.
   • Iteratief worden paren van knopen ($u, v$) samengevoegd op basis van de "meest vergelijkbare" paren in de matrix $D$, maar alleen als ze ook als buren worden beschouwd in de constraint-netwerken ($C_i$).
   • Tijdens het samenvoegen worden reticulatie-informatie (hybride relaties) uit de constraint-netwerken vastgelegd en later toegevoegd aan het eindnetwerk.
   • Als er conflicten ontstaan bij het samenvoegen van meer dan twee constraint-netwerken, wordt een recursieve aanpak gebruikt (Algorithm 5) om de netwerken paarsgewijs te mergen totdat er één overblijft.

Theoretische Basis:
De auteurs bewijzen dat deze pipeline statistisch consistent is onder het multispecies network coalescent (MSNC) model, mits de input-methoden (voor de constraint-netwerken en de dissimilariteitsmatrix) zelf statistisch consistent zijn en de subsets op een specifieke manier worden geselecteerd (zodat hybride clades niet worden gescheiden).

3. Belangrijkste Bijdragen

• Schaalbaarheid: InPhyNet bereikt een lineaire schaalbaarheid ($O(N)$) met betrekking tot het aantal taxa, in tegenstelling tot de exponentiële of hoge polynoom complexiteit van bestaande methoden.
• Statistische consistentie: Er is een wiskundig bewijs geleverd dat de methode de ware soortnetwerken kan herstellen bij voldoende data.
• Open-source implementatie: De code is beschikbaar als een Julia-package (InPhyNet.jl).
• Empirische validatie: De methode is getest op simulaties met tot 200 taxa en toegepast op een reële dataset van 1.158 landplanten.

4. Resultaten

Simulatiestudie:

• Nauwkeurigheid: De nauwkeurigheid van InPhyNet is sterk afhankelijk van de nauwkeurigheid van de invoer-netwerken (de constraint-netwerken). Er is een sterke correlatie tussen de invoerfout en de uitvoerfout.
• Invloed van parameters: De grootte van de constraint-netwerken ($m$) had weinig invloed op de nauwkeurigheid, maar had een direct negatief effect op de runtime. Grotere $m$-waarden vertragen de berekening aanzienlijk.
• Methodenvergelijking: Methoden zoals SNaQ, PhyloNet-ML en PhyloNet-MPL leverden vergelijkbare nauwkeurigheid op wanneer ze werden gebruikt als constraint-invoer, maar PhyloNet-MPL was het snelst.
• Schaalbaarheid: Voor een vaste $m$ nam de totale runtime lineair toe met het aantal taxa. Netwerken met 200 taxa konden binnen een haalbare tijd worden geïnfereerd.

Empirische Toepassing (Landplanten):
De auteurs herbewerkten de fylogenie van 1.158 landplanten (uit het One Thousand Plant Transcriptomes Initiative):

• Ze identificeerden gebieden met conflicterende signalen (vooral binnen gymnospermen en varens) die slecht werden opgelost door traditionele bomen.
• Gnetales: Het netwerk ondersteunde een hybride hypothese voor de plaatsing van Gnetales, wat gedeeltelijk zowel de "Gnetifer" (zuster van coniferen) als "Gnepine" (zuster van Pinaceae) hypotheses ondersteunt.
• Pinaceae en Polypodiidae: Er werden reticulaties gevonden die overeenkomen met bekende polyploïdisatie- en hybridisatie-evenementen in deze groepen.
• Het resultaat is een coherent, semi-gericht netwerk dat de evolutionaire geschiedenis van groene planten expliciet accounteert voor netwerkvormende evolutie.

5. Betekenis en Conclusie

InPhyNet opent de deur voor massief schaalbare fylogenetische netwerkanalyses. Het lost het fundamentele probleem op dat nauwkeurige netwerkinferentie tot nu toe beperkt was tot kleine datasets.

• Het combineert de nauwkeurigheid van geavanceerde likelihood-methoden (op kleine schaal) met de snelheid van divide-and-conquer strategieën.
• Het stelt onderzoekers in staat om complexe evolutionaire geschiedenissen, inclusief hybridisatie, te bestuderen op schalen van honderden tot duizenden soorten, wat cruciaal is voor het begrijpen van biodiversiteit, ziekte-uitbraken en landbouwdomesticatie.
• De studie benadrukt dat de kwaliteit van de input-data (de constraint-netwerken) de doorslaggevende factor is voor de uiteindelijke nauwkeurigheid, wat betekent dat de keuze van de onderliggende inferentiemethode en de datasetkwaliteit essentieel blijven.