STEQ: A statistically consistent quartet distance based species tree estimation method

Dit artikel introduceert STEQ, een snelle en nauwkeurige statistisch consistente afstandsmethode voor het schatten van soortbomen op grote schaal die, hoewel het aanzienlijk sneller is dan toonaangevende methoden zoals ASTRAL, vergelijkbare prestaties behaalt.

De kern

Stel je voor dat je een enorme familiegeschiedenis wilt reconstrueren, maar je hebt geen enkele foto van de hele familie. Je hebt alleen duizenden losse foto's van kleine groepjes verwanten (bijvoorbeeld een foto van twee broers, een foto van een oom en een nicht, etc.). Het probleem is dat deze foto's soms tegenstrijdig zijn. Misschien lijkt het op de ene foto alsof broer A het dichtst bij oom B staat, maar op een andere foto staat broer A dichter bij nicht C. Dit komt doordat in de echte geschiedenis van het leven (evolutie) er vaak verwarring ontstaat: soms vererven eigenschappen niet precies zoals je zou verwachten.

In de biologie noemen we deze losse foto's genen (of gen-boomtjes) en de hele familiegeschiedenis de soortenboom. De uitdaging voor wetenschappers is om uit al die duizenden, soms tegenstrijdige, kleine foto's één grote, juiste familieboom te maken.

Het probleem met de oude methoden

Tot nu toe waren er twee manieren om dit te doen:

1. De "Plak-er-alles-op" methode: Je plakt alle foto's aan elkaar tot één gigantisch plaatje. Dit werkt vaak snel, maar kan leiden tot een verkeerde conclusie omdat de tegenstrijdigheden worden genegeerd.
2. De "Super-rekenaar" methode: Je laat een computer heel nauwkeurig elke kleine foto analyseren om te zien welke combinatie het meest logisch is. Dit geeft vaak het beste resultaat, maar het is zo traag dat het duurt om de boom te maken voor grote groepen dieren of planten. Het is alsof je een puzzel van 10.000 stukjes probeert te leggen door elk stukje één voor één met de hand te controleren.

De nieuwe oplossing: STEQ

De auteurs van dit paper hebben STEQ bedacht. Dit is een nieuwe, slimme manier om die grote familieboom te maken. Je kunt STEQ vergelijken met een slimme schattingstechniek in plaats van een zware berekening.

Hier is hoe het werkt, in simpele termen:

1. Het "Vier-Persoons" Spelletje

In plaats van naar de hele boom te kijken, kijkt STEQ naar kleine groepjes van vier soorten (we noemen dit kwartetten).

• Stel je hebt vier mensen: A, B, C en D.
• STEQ vraagt zich af: "Wie staan het dichtst bij elkaar?"
• Als A en B het meest op elkaar lijken, en C en D het meest, dan is de verhouding: (A+B) tegenover (C+D).

2. De Afstandsmeter

STEQ berekent voor elk paar soorten (bijvoorbeeld A en B) een soort "afstand". Maar hoe meet je die afstand?

• Het telt in hoeveel van die duizenden kleine foto's (genen) A en B aan tegengestelde kanten van een verdelingslijn staan.
• De analogie: Stel je voor dat je in een grote zaal staat. Als A en B vaak aan de andere kant van de zaal van elkaar staan in de verschillende foto's, dan zijn ze ver van elkaar verwijderd in de evolutie. Als ze vaak aan dezelfde kant staan, zijn ze familie.

3. De Slimme Correctie (Normalisatie)

Hier komt de echte genialiteit van STEQ. Soms kan de berekening "opblazen" door toevallige grote groepen.

• Voorbeeld: Stel je hebt een foto van twee broertjes (A en B) en daarnaast een groep van 96 vreemden. Als je gewoon telt, wegen die 96 vreemden misschien te zwaar mee in de berekening, alsof ze heel belangrijk zijn voor de relatie tussen de twee broertjes.
• STEQ heeft een slimme correctie bedacht die zegt: "Wacht even, die 96 vreemden tellen niet mee voor de relatie tussen deze twee broertjes." Hierdoor wordt de berekening veel eerlijker en nauwkeuriger, vooral bij heel grote datasets.

4. De Snelheid

Dit is het grootste voordeel.

• De oude methoden (zoals ASTRAL) moeten vaak alle mogelijke combinaties van vier soorten uitrekenen. Dat is als proberen elke mogelijke route door een stad te lopen om de kortste weg te vinden.
• STEQ gebruikt een slimme truc om de afstand direct te berekenen zonder alles uit te rekenen. Het is alsof je een GPS gebruikt die direct de snelste route berekent, in plaats van alle wegen af te lopen.
• Resultaat: STEQ is veel sneller. Waar andere methoden uren of zelfs dagen nodig hebben voor grote datasets (zoals duizenden vogelsoorten), doet STEQ dit in minuten.

Wat hebben ze bewezen?

De auteurs hebben STEQ getest op:

1. Gesimuleerde data: Computergegenereerde familieboomen waar ze de "juiste" oplossing kenden. STEQ bleek net zo goed (soms zelfs beter) te zijn als de beste bestaande methoden, maar dan veel sneller.
2. Echte data: Ze hebben het gebruikt op echte datasets, zoals:
   • Planten: Een dataset met bijna 1.200 plantensoorten. STEQ kon de grote families van planten correct groeperen.
   • Vogels: Een dataset met 363 vogelsoorten en maar liefst 63.000 genen. STEQ kon de evolutie van vogels (zoals de relatie tussen pinguïns, adelaars en zangers) correct reconstrueren, en deed dit in 3 uur, terwijl andere methoden daar 2,5 dag over deden.

Conclusie

STEQ is als een snelle, slimme en betrouwbare navigator voor de evolutiebiologie. Het lost het probleem op van "te veel data" door slimme wiskunde te gebruiken in plaats van brute kracht. Het maakt het mogelijk om de levensboom van duizenden soorten in een handomdraai te reconstrueren, zonder dat de nauwkeurigheid eronder lijdt. Dit opent de deur voor wetenschappers om veel grotere en complexere evolutionaire mysteries op te lossen dan ooit tevoren.

Technische samenvatting

Probleemstelling

Het nauwkeurig schatten van soortbomen (species trees) uit multi-locus data is een fundamentele maar uitdagende taak in de fylogenomica. Een groot obstakel is genboom-discordantie (gene tree discordance), waarbij de evolutionaire geschiedenis van individuele genen verschilt van die van de soort. Dit fenomeen wordt vaak veroorzaakt door onvolledige lijnagescheiding (Incomplete Lineage Sorting - ILS), gemodelleerd door het multi-species coalescent (MSC) model.

Bestaande methoden om dit op te lossen vallen in twee categorieën:

1. Samenvattingsmethoden (Summary methods): Methoden zoals ASTRAL en wQFM-TREE zijn statistisch consistent en zeer nauwkeurig, maar ze zijn computationeel zwaar en schalen slecht naar grote datasets (duizenden taxa en genen).
2. Concatenatie: Het samenvoegen van alle sequenties in één "supergene" is vaak statistisch inconsistent en kan misleidende resultaten opleveren.

Er is een dringende behoefte aan methoden die zowel snel (schaalbaar) als statistisch consistent zijn voor het analyseren van grote fylogenomische datasets.

Methodologie: STEQ

De auteurs introduceren STEQ (Species Tree Estimation using Quartet distance), een nieuwe afstand-gebaseerde methode die gebruikmaakt van kwartet-afstanden.

1. Kwartet-afstandsberekening:
STEQ berekent de afstand tussen twee taxa $x$ en $y$ op basis van de gemiddelde kwartet-afstand over alle genenbomen.

• Een kwartet $q = ab|cd$ bestaat uit vier taxa.
• De afstand $QD_{gt}(x, y)$ in een specifieke genboom wordt gedefinieerd als het aantal kwartetten waarin $x$ en $y$ aan tegengestelde kanten van de interne knoop liggen.
• In plaats van kwartetten expliciet te enumereren (wat $O(n^4k)$ kost), berekent STEQ deze afstand efficiënt door door de interne knopen op het pad tussen $x$ en $y$ in de genboom te traverseren.
• De formule voor de bijdrage van een interne knoop $u$ met een tripartition $X|Y|Z$ (waarbij $x \in X$ en $y \in Y$) is:
  $$QD_u(x, y) = \binom{|X|-1}{1}|Z| + \binom{|Y|-1}{1}|Z|$$
  De totale afstand is de som van deze bijdragen, gedeeld door 2 (omdat elk kwartet twee interne knopen heeft).

2. Genormaliseerde Kwartet-afstand:
De auteurs stellen vast dat de standaardformule de afstand kan overdrijven wanneer een derde partitie $Z$ zeer groot is (wat vaak voorkomt bij ondiepe interne knopen). Om dit op te lossen, introduceren ze een genormaliseerde kwartet-afstand:
$$NQD_u(x, y) = (|X| - 1) + (|Y| - 1)$$
Hierdoor wordt de afhankelijkheid van de grootte van $Z$ verwijderd, waardoor de focus ligt op de lokale topologische structuur. Dit verbetert de nauwkeurigheid zonder de statistische consistentie te schaden.

3. Boomreconstructie:
Na het berekenen van de $n \times n$ afstandsmatrix (waarbij $n$ het aantal taxa is), wordt de soortboom geschat met behulp van bestaande afstand-gebaseerde algoritmen: FastME (als er geen ontbrekende taxa zijn) of BioNJ (als er ontbrekende taxa zijn in de genenbomen).

4. Statistische Consistentie:
De auteurs bewijzen wiskundig dat de kwartet-afstand additief is op het ware soortboom onder het MSC-model. Hieruit volgt dat STEQ een statistisch consistente methode is; met voldoende data convergeert de geschatte boom naar het ware soortboom.

Belangrijkste Bijdragen

• Nieuwe Methode: STEQ is een snelle, statistisch consistente en schaalbare methode voor soortboom-schatting.
• Efficiëntie: De tijdscomplexiteit is $O(k n^2 \log n)$ voor $n$ taxa en $k$ genen (bij gebalanceerde bomen). Dit is asymptotisch sneller dan toonaangevende methoden zoals ASTRAL.
• Genormaliseerde Afstand: Een nieuwe normalisatietechniek die de nauwkeurigheid verbetert door de invloed van grote, irrelevante taxagroepen te verminderen.
• Open Source: De software is beschikbaar op GitHub.

Resultaten

De auteurs evalueerden STEQ op zowel gesimuleerde als empirische datasets en vergeleken het met ASTRAL-III en wQFM-TREE.

1. Nauwkeurigheid:

• Gesimuleerde Data: STEQ behaalde vergelijkbare of superieure nauwkeurigheid ten opzichte van ASTRAL en wQFM-TREE over een breed scala aan scenario's (variërend in aantal taxa, genen en ILS-niveau).
• Empirische Data:
  • Op een plantendataset (1.178 taxa, 410 genen) herstelde STEQ alle grote claden consistent met gevestigde methoden.
  • Op een uitgebreide vogeldataset (363 soorten, 63.430 genen) reconstrueerde STEQ correct de drie grote vogelgroepen (Palaeognathae, Galloanseres, Neoaves) en de belangrijkste clades binnen Neoaves.

2. Snelheid en Schaalbaarheid:
STEQ is aanzienlijk sneller dan de concurrenten, vooral bij grote datasets:

• 200 taxa / 1000 genen: STEQ: ~30 sec vs. ASTRAL/wQFM: 4-6 min.
• 500 taxa: STEQ: ~4 min vs. ASTRAL/wQFM: 25-40 min.
• 1000 taxa: STEQ: <20 min vs. ASTRAL/wQFM: 2-3 uur.
• Empirisch (1178 taxa): STEQ: ~7 min vs. ASTRAL: ~1 uur.
• Empirisch (363 taxa, 63k genen): STEQ: ~3 uur vs. ASTRAL: ~1 dag.

Betekenis en Conclusie

STEQ vult een cruciale kloof in de fylogenomica door een methode te bieden die de snelheid van afstand-gebaseerde methoden combineert met de statistische consistentie van coalescent-gebaseerde samenvattingsmethoden.

De methode maakt het mogelijk om soortbomen voor datasets met duizenden taxa en tienduizenden genen te analyseren in plaats van uren of dagen, zonder in te leveren op nauwkeurigheid. Dit is van groot belang voor de analyse van grote fylogenomische projecten. De auteurs merken op dat de huidige implementatie single-core is en dat toekomstig werk gericht zal zijn op parallelisatie en uitbreiding naar triplet-metrieken.