k-Nearest Common Leaves algorithm for phylogenetic tree completion

Dit paper introduceert het k-Nearest Common Leaves (k-NCL) algoritme, een O(n²)-methode voor het aanvullen van gefaseerde fylogenetische bomen met overlappende taxa door gebruik te maken van taklengtes en topologie, wat leidt tot een verbeterde clusteringprestatie vergeleken met bestaande methoden.

De kern

De "K-Naaste Vrienden" Methode: Hoe we evolutionaire familieboeken samenvoegen

Stel je voor dat je twee verschillende familiealbums hebt. In het ene album staan foto's van je oom, tante en neefjes. In het andere album staan foto's van je oom, tante en een paar nieuwe neefjes die je in het eerste album mist. Beide albums vertellen het verhaal van dezelfde familie, maar ze zijn niet compleet en ze hebben verschillende foto's.

In de wereld van de biologie doen wetenschappers precies hetzelfde met stamboomdiagrammen (phylogenetische bomen). Deze bomen tonen hoe soorten (zoals vogels, haaien of mensen) met elkaar verwant zijn. Het probleem is: vaak hebben twee onderzoekers twee verschillende bomen. De ene heeft data over 50 soorten, de andere over 60 soorten, en ze delen maar 40 soorten.

Hoe vergelijk je deze bomen dan?

1. De oude manier (Knippen): Je knipt gewoon alle unieke soorten weg en vergelijkt alleen de 40 die ze gemeen hebben. Dit is als het wegdoen van de foto's van je nieuwe neefjes omdat ze niet in het andere album staan. Je verliest dan belangrijke informatie.
2. De nieuwe manier (Invullen): Je probeert de ontbrekende foto's in het ene album te "invullen" op basis van het andere album, zodat je twee volledige albums hebt om te vergelijken.

Deze paper introduceert een slimme nieuwe methode om die invulling te doen, genaamd k-Naaste Gemeenschappelijke Bladeren (of in het Engels: k-Nearest Common Leaves, kortweg k-NCL).

Hoe werkt deze nieuwe methode?

Stel je voor dat je de "nieuwe neefjes" (de soorten die in boom A staan, maar niet in boom B) moet toevoegen aan boom B. Waar moet je ze plakken?

1. De "K-Naaste Vrienden" regel
De methode kijkt naar de soorten die in beide bomen voorkomen (de gemeenschappelijke bladeren). Voor elke nieuwe soort die je wilt toevoegen, zoekt de computer de k (bijvoorbeeld 3) soorten in de bestaande boom die het dichtst bij die nieuwe soort zitten.

• Analogie: Als je een nieuwe foto van een neefje wilt toevoegen aan je familiealbum, kijk je niet naar willekeurige mensen. Je kijkt naar zijn drie naaste familieleden die je al kent. Waar zitten zij in het album? Dan plakt je de nieuwe foto daar vlakbij.

2. Het rekening houden met de "snelheid" van evolutie
Soms groeien bomen in verschillende snelheden. In boom A heeft een tak misschien 10 miljoen jaar evolutie vertegenwoordigd, terwijl in boom B dezelfde tak eruitziet alsof het maar 5 miljoen jaar is.
De k-NCL-methode is slim genoeg om dit te merken. Het past de lengte van de takken aan (zoals het rekken of krimpen van een elastiek) zodat de tijdsafstanden kloppen voordat hij de nieuwe takken toevoegt.

• Analogie: Stel je voor dat je een foto van iemand toevoegt aan een album, maar die persoon is in een andere tijdzone opgegroeid. Je moet de foto iets "schalen" zodat hij past bij de tijdlijn van het album, anders klopt de chronologie niet.

3. De perfecte plek vinden
De computer berekent precies waar de nieuwe tak het beste past. Het zoekt naar een plek op een bestaande tak waar de afstanden naar de "k naaste vrienden" het meest logisch zijn. Het is alsof je een puzzelstukje zoekt dat niet alleen qua vorm past, maar ook qua kleur en patroon perfect aansluit bij de stukjes eromheen.

Waarom is dit zo belangrijk?

• Geen informatieverlies: In tegenstelling tot het oude "knippen", houden we alle soorten. We verliezen geen unieke informatie.
• Snel en efficiënt: De methode is snel genoeg om zelfs met enorme datasets (duizenden soorten) om te gaan.
• Betrouwbare resultaten: De auteurs hebben dit getest op echte dieren (amfibieën, vogels, zoogdieren en haaien). Ze ontdekten dat wanneer je deze nieuwe methode gebruikt om bomen te vergelijken, je veel scherpere en duidelijkere groepen (clusters) krijgt. Het is alsof je met een wazige bril kijkt versus een scherp vizier: je ziet de familiebanden veel duidelijker.

Samenvatting in één zin

De k-NCL methode is een slimme manier om twee onvolledige evolutionaire stambomen met elkaar te verenigen door de ontbrekende stukjes op de meest logische plek te plakken, rekening houdend met zowel de vorm van de boom als de tijd die erin zit, zodat we een completer en accurater beeld van de evolutie krijgen.

Technische samenvatting

Titel: k-Nearest Common Leaves (k-NCL) algoritme voor het voltooien van fylogenetische bomen

Auteurs: Aleksandr Koshkarov en Nadia Tahiri (Universiteit van Sherbrooke, Canada)

---

1. Het Probleem

Fylogenetische bomen worden gebruikt om de evolutionaire geschiedenis van taxa weer te geven. Een veelvoorkomende taak in de evolutionaire biologie is het meten van de afstand tussen bomen om ze te vergelijken, te clusteren of een "Tree of Life" te reconstrueren.

• De uitdaging: Bestaande vergelijkingsmethoden, zoals de Robinson-Foulds (RF) afstand, veronderstellen dat de bomen dezelfde set van soorten (taxa) bevatten. In de praktijk hebben bomen echter vaak overlappende maar niet-identieke sets van taxa.
• Bestaande oplossingen en hun tekortkomingen:
  • Pruning (Snoeien): Het verwijderen van niet-gemeenschappelijke bladeren. Dit leidt tot verlies van waardevolle evolutionaire informatie.
  • Voltooiing (Completion): Het toevoegen van ontbrekende taxa aan beide bomen zodat ze op dezelfde set zijn gedefinieerd. Bestaande methoden voor voltooiing (zoals RF(+)) negeren vaak de taklengtes (branch lengths), die essentieel zijn voor het begrijpen van evolutionaire patronen en tijdschalen. Andere methoden die wel taklengtes gebruiken (zoals geodesische afstanden in de BHV-ruimte) zijn vaak computationeel te intensief voor grote datasets.

2. Methodologie: Het k-NCL Algoritme

De auteurs introduceren k-Nearest Common Leaves (k-NCL), een algoritme dat twee wortelbomen met overlappende taxa compleet maakt tot één uniforme set taxa, waarbij zowel topologie als taklengtes worden behouden.

Kernstappen van het algoritme:

1. Identificatie van Subtrees: Het algoritme identificeert "maximale distinct-leaf subtrees" (subbomen die alleen bestaan uit bladeren die uniek zijn voor één van de twee bomen).
2. Schaal aanpassing (Branch Length Adjustment): Omdat de evolutionaire snelheden tussen twee bomen kunnen verschillen, wordt een globale aanpassingsrate ($r$) berekend. Dit is de verhouding tussen de totale paarsgewijze afstanden van de gemeenschappelijke bladeren in boom $T_1$ en boom $T_2$. De taklengtes van de te introduceren subtrees worden geschaald met deze rate om ze compatibel te maken met de doelboom.
3. Selectie van Referentiepunten (k-NCL): Voor elke te introduceren subtree worden de $k$ dichtstbijzijnde gemeenschappelijke bladeren ($N_k$) in de bronboom geselecteerd op basis van hun afstand tot de wortel van de subtree.
4. Locatiebepaling (Insertion Point):
   • Er wordt een position distance berekend voor de subtree in de doelboom, gebaseerd op de afstanden tot de $k$ geselecteerde gemeenschappelijke bladeren en een lokale schaalfactor.
   • Het algoritme zoekt de optimale invoeglocatie op de bestaande takken van de doelboom door een kwadratische objectieve functie te minimaliseren. Deze functie meet de discrepantie tussen de waargenomen afstanden in de doelboom en de berekende positie-afstanden.
   • De invoeglocatie kan een bestaand knooppunt zijn of een punt op een tak (waarbij de tak wordt gesplitst).
5. Invoegen: De geschaalde subtree wordt op de geoptimaliseerde locatie ingevoegd. Dit proces wordt herhaald voor alle unieke subtrees in beide richtingen (van $T_1$ naar $T_2$ en vice versa).

Technische specificaties:

• Complexiteit: $O(n^2)$ voor een vaste $k$, waarbij $n$ de grootte is van de vereniging van de twee bladsets.
• Datastructuren: Gebruik van een "distance oracle" (gebaseerd op Euler-tours en RMQ) om afstandsberekeningen tussen knooppunten in $O(1)$ uit te voeren.

3. Belangrijkste Bijdragen

1. Integratie van Taklengtes: In tegenstelling tot topologie-only methoden (zoals RF(+)), houdt k-NCL rekening met evolutionaire afstanden (taklengtes), wat leidt tot een nauwkeurigere weergave van evolutionaire signalen.
2. Schaalstrategie: Een innovatieve methode om verschillen in evolutionaire snelheden tussen bomen te compenseren via globale en lokale schalingsfactoren.
3. Onafhankelijkheid van Afstandsmaten: Het algoritme is niet afhankelijk van een specifieke afstandsmaat (zoals RF of BHV-geodesiek) voor de voltooiing zelf; het optimaliseert puur op basis van de interne consistentie van de bomen.
4. Eigenschappen: Het algoritme garandeert:
   • Behoud van de oorspronkelijke topologie en taklengtes van de ingevoerde bomen.
   • Symmetrie (de volgorde van invoer maakt niet uit).
   • Uniekheid van de oplossing.
   • Toepasbaarheid op zowel binaire als niet-binaire (multifurcerende) bomen.
5. Implementatie: Een open-source Python-implementatie is beschikbaar.

4. Resultaten en Evaluatie

De auteurs hebben k-NCL geëvalueerd op biologische datasets van amfibieën, vogels, zoogdieren en haaien.

• Invloed van parameter $k$: Experimenten tonen aan dat de kwaliteit van de voltooiing verbetert naarmate $k$ toeneemt, maar dat er een verzadigingspunt is. De waarde $k = \lfloor (N_{cl} + 2) / 2 \rfloor$ (ongeveer de helft van het aantal gemeenschappelijke bladeren) bleek een goede standaardwaarde te zijn.
• Vergelijking met Pruning (BSD(-) vs. BSD(k-NCL)):
  • Er is een conflict gevonden in ongeveer 8% van de vergelijkingen tussen het gebruik van pruning en het gebruik van k-NCL.
  • Bij lage tot middelhoge overlap (Jaccard-coëfficiënt < 0.4) levert k-NCL vaak een informatiever resultaat op, terwijl pruning waardevolle data verwijdert.
• Clustering Prestaties:
  • De prestaties van k-NCL werden vergeleken met de RF(+) methode (topologie-only) en de klassieke RF-maatstaf.
  • RF(k-NCL) (topologie van k-NCL bomen) en BSD(k-NCL) (Branch Score Distance op k-NCL bomen) presteerden aanzienlijk beter bij het identificeren van correcte clusters dan RF(+).
  • Met name RF(k-NCL) behaalde de hoogste Silhouette-scores en Dunn-indexen, wat aantoont dat k-NCL de clusterstructuur van overlappende bomen beter behoudt dan bestaande methoden.

5. Betekenis en Conclusie

Het k-NCL-algoritme vult een belangrijke methodologische lacune in de fylogenetische analyse. Het biedt een robuuste, computationeel haalbare oplossing voor het vergelijken van bomen met verschillende taxa sets zonder informatie te verliezen door pruning en zonder de complexiteit van volledige BHV-geodesische berekeningen.

De belangrijkste implicatie is dat het behoud van taklengtes tijdens het voltooiingsproces cruciaal is voor het behoud van evolutionaire relaties. Door zowel topologie als tijdschalen te integreren, verbetert k-NCL de nauwkeurigheid van downstream-taken zoals clustering en het reconstrueren van de "Tree of Life". De methode is bijzonder waardevol in scenario's met beperkte overlap tussen datasets, waar traditionele pruning-methoden falen.