Sequence-to-graph alignment based copy number calling using a network flow formulation

Het artikel introduceert Floco, een methode die netwerkvloei-optimisatie toepast op aligneringen in een genoomgraf om de nauwkeurigheid van copy number-bepaling aanzienlijk te verbeteren ten opzichte van traditionele lineaire referentie-gebaseerde benaderingen.

De kern

De Kern: Een Nieuwe Manier om Genen te "Tell"

Stel je voor dat ons DNA een gigantische bibliotheek is. In deze bibliotheek staan boeken (genen) die instructies geven voor hoe ons lichaam werkt. Soms gebeurt er iets interessants: een boek wordt niet één keer, maar twee, drie of zelfs tien keer gekopieerd. Of juist helemaal niet. Dit noemen we kopieaantal-variatie (in het Engels: Copy Number Variation of CNV).

Als je te veel of te weinig kopieën van een bepaald boek hebt, kan dat leiden tot ziekten of andere kenmerken. De uitdaging voor wetenschappers is om deze kopieën nauwkeurig te tellen.

Het Oude Probleem: De Eenzame Straatkaart

Vroeger probeerden wetenschappers dit te doen door alle DNA-fragmenten (de "bladzijdes" uit de bibliotheek) te vergelijken met één enkele, standaard lijnformule (een lineaire referentie).

• De Analogie: Stel je voor dat je een stad probeert te navigeren met een oude, platte kaart die alleen rechte straten laat zien. Als er in de echte stad echter een rondje, een brug of een doodlopende steeg is die niet op je kaart staat, raak je verdwaald.
• Het probleem: Menselijk DNA is niet altijd een rechte lijn. Het heeft bochten, lusjes en variaties. Als je alleen naar een rechte lijn kijkt, mis je belangrijke details of telt je verkeerd, omdat je probeert een complex 3D-gebouw in te passen op een 2D-tekening.

De Oplossing: Floco en het Netwerk van Sporen

De auteurs van dit paper hebben een nieuwe tool bedacht die Floco heet. In plaats van naar één rechte lijn te kijken, kijken ze naar een DNA-kaart die eruitziet als een ingewikkeld web of een stadsplan met veel kruispunten (een genoomgrafiek).

Floco werkt als een slimme verkeersleider die gebruikmaakt van een stroomnetwerk (network flow).

1. De Sporen (Leesjes): Wanneer we DNA sequencen, krijgen we duizenden kleine stukjes DNA (leesjes). Deze worden op de kaart gelegd.
2. De Ruwe Schatting: Eerst telt Floco simpelweg hoeveel sporen er op elk stukje van de kaart liggen.
   • Analogie: Als je op een brug 10 auto's ziet rijden, denk je misschien: "Hier is veel verkeer." Maar als je alleen naar die ene brug kijkt, weet je niet of die auto's daar vandaan komen of er juist heen gaan. Soms telt je verkeerd door ruis of fouten.
3. De Slimme Berekening (Stroomnetwerk): Hier komt Floco's genialiteit om de hoek kijken. In plaats van elke brug apart te tellen, kijkt Floco naar het hele netwerk.
   • Het stelt de vraag: "Als er 10 auto's de stad binnenkomen, moeten er dan ook 10 auto's de stad weer verlaten?"
   • Het zorgt ervoor dat het totale verkeer logisch door het hele netwerk stroomt. Als er een stukje kaart is waar de telling niet klopt (bijvoorbeeld omdat een auto verkeerd is geparkeerd), corrigeert Floco dit door te kijken naar de buren.
   • Het gebruikt wiskunde (specifiek Integer Linear Programming) om de meest waarschijnlijke route te vinden die het hele plaatje logisch maakt.

Waarom is dit zo goed?

De onderzoekers hebben Floco getest op verschillende soorten data (zoals HiFi en ONT sequencing, wat verschillende manieren zijn om DNA te lezen).

• Resultaat: Door het gebruik van dit "stroomnetwerk" werd de nauwkeurigheid tot 43% beter dan de oude methode die alleen naar de hoeveelheid sporen keek.
• Betrouwbaarheid: Als je dezelfde persoon meet met drie verschillende methoden (verschillende technologieën), kwamen de resultaten van Floco in 93% van de gevallen overeen. Dat is alsof drie verschillende mensen die een gebouw tellen, bijna altijd precies hetzelfde aantal ramen vinden.

Twee Toepassingen

Floco is nuttig voor twee dingen:

1. Kwaliteitscontrole (De Bouwkeuring): Als wetenschappers een nieuw DNA-kaartje maken (een assemblage), kan Floco fouten vinden. Als er een stukje kaart is waar geen auto's rijden (geen kopieën), terwijl het wel zou moeten, weet je dat er een fout in de kaart zit. Het helpt om "dode hoeken" in de kaart te vinden.
2. Ziekten Opsporen (De Detective): Het helpt om te zien of iemand extra kopieën van een gen heeft (bijvoorbeeld bij bepaalde ziektes). Omdat Floco kijkt naar het hele netwerk, ziet het variaties die de oude, rechte lijn-methodes over het hoofd zouden zien.

Samenvatting in één zin

Floco is als een slimme verkeersleider die niet alleen naar het aantal auto's op één brug kijkt, maar het hele verkeersnetwerk in de gaten houdt om zo fouten te corrigeren en precies te tellen hoeveel kopieën van een gen er echt zijn, zelfs in de meest ingewikkelde delen van ons DNA.

Dit maakt het een krachtig hulpmiddel voor het vinden van ziekteoorzaken en het maken van betere, nauwkeurigere kaarten van het menselijk genoom.

Technische samenvatting

Probleemstelling

Traditionele methoden voor het bepalen van kopieaantallen (Copy Number, CN) van DNA-segmenten vertrouwen op het mappen van sequencing reads op een lineaire referentie-genoom. Deze aanpak heeft twee fundamentele beperkingen:

1. Referentie-bias: Sequences en genomische herschikkingen die niet aanwezig zijn in de lineaire referentie worden genegeerd of verkeerd gemapt.
2. Inconsistentie in grafische benaderingen: Hoewel pangenoom-grafieken (die meerdere haplotypes en variaties bevatten) deze bias verminderen, leiden eenvoudige CN-schattingen per grafiek-knooppunt (node) vaak tot inconsistenties. Omdat de CN-waarden niet noodzakelijk consistent zijn over de hele grafiek (d.w.z. ze kunnen niet altijd worden vertaald naar geldige paden door de grafiek), ontstaan er fouten door sequencing-fouten, verkeerde alignments of misassemblies.

Er is een behoefte aan een methode die CN-calling uitvoert op grafieken, waarbij gebruik wordt gemaakt van de grafiek-topologie om deze inconsistenties op te lossen.

Methodologie: Floco

De auteurs stellen Floco voor, een methode voor CN-calling op genoom-grafieken die gebruikmaakt van een netwerkstroom-formulering (network flow) opgelost met Integer Linear Programming (ILP).

Het proces verloopt als volgt:

1. Input: Een genoom-grafiek (in GFA-formaat) en alignments van reads tegen die grafiek (in GAF-formaat).
2. Basis CN-kansen: Voor elke knooppunt in de grafiek wordt de ruime dekking (coverage) berekend. Op basis van een Negatieve Binomiale verdeling (voor CN > 0) en een exponentiële verdeling (voor CN = 0, om aligneringsfouten te modelleren) worden kansen berekend voor verschillende CN-waarden per knooppunt.
3. Netwerkstroom Formulering:
   • De grafiek wordt omgezet in een stroomnetwerk met een supersource ($s$) en een supersink ($t$).
   • Elke knooppunt heeft twee uiteinden (links en rechts) die verbonden zijn met de source en sink.
   • Het doel is om een stroom te vinden die de totale waarschijnlijkheid maximaliseert (of kosten minimaliseert), waarbij de stroom door de grafiek de CN-waarden vertegenwoordigt.
   • Constraints:
     • De inkomende stroom aan de ene kant van een knooppunt moet gelijk zijn aan de uitgaande stroom aan de andere kant (behoud van stroom).
     • De som van de stroom door een knooppunt moet overeenkomen met de geschatte CN van dat knooppunt.
     • Er zijn kosten (penalties) gekoppeld aan het gebruik van randen (edges) die weinig ondersteuning hebben van reads, en aan het gebruik van "superedges" (verbindingen met source/sink) die niet nodig zijn.
4. Optimalisatie: Het probleem wordt opgelost als een maximalisatie-probleem (maximaliseren van de log-probabiliteit van de CN-toewijzingen plus de randkosten) met behulp van de ILP-solver Gurobi. Dit zorgt ervoor dat de CN-toewijzingen over de hele grafiek consistent zijn en dat lokale ruis wordt gecorrigeerd.

Belangrijkste Bijdragen

• Eerste tool voor grafiek-gebaseerde CN-calling: Floco vult een gat in het ecosysteem van tools voor genoom-grafieken door CN-calling te koppelen aan de grafiek-topologie.
• Netwerkstroom voor consistentie: In plaats van knooppunten geïsoleerd te behandelen, gebruikt Floco een stroommodel om ervoor te zorgen dat CN-waarden consistent zijn over de gehele grafiek, waardoor fouten door lokale dekkingsschommelingen worden gecorrigeerd.
• Robuustheid: De methode werkt met verschillende databronnen (HiFi, ONT, en gesplitste lineaire assemblies) en is toepasbaar op zowel assemblage-grafieken als pangenoom-grafieken.

Resultaten

De auteurs testten Floco op 15 datasets met drie verschillende grafieken:

1. Assemblage QC: Toepassing op assemblage-grafieken van een diploïde mens (HG01114) en een tetraploïde aardappel (Altus).
2. Pangenoom: Toepassing op de HPRC pangenoom-grafiek met in-sample (CHM13, HG01258) en out-of-sample (HG01114) data.

Kernbevindingen:

• Verbeterde Nauwkeurigheid: Het toevoegen van de netwerkstroom-formulering verhoogde de nauwkeurigheid van CN-predicties met tot 43% in vergelijking met schattingen op basis van alleen read-depth (zonder stroom).
• Vergelijking met Ground Truth (CHM13): Voor CHM13 (waar de ground truth bekend was) bereikte Floco een nauwkeurigheid van 99,7% voor knooppunten (na flow), vergeleken met 99,6% voor de chopped assembly. Zonder flow was de nauwkeurigheid lager (bijv. 97,2% voor HiFi).
• Concordantie tussen technologieën: De overeenkomst tussen CN-predicties van HiFi, ONT en chopped assemblies was zeer hoog. Voor de menselijke assemblage-grafiek bereikte de concordantie 93,2% van de totale sequentielengte.
• Kwaliteitscontrole: Floco slaagde erin om misassemblies te detecteren door knooppunten met CN=0 te flaggen, zelfs als er enige dekking aanwezig was (vaak veroorzaakt door bubbel-structuren in de grafiek die door de assembler niet konden worden opgelost).
• Efficiëntie: Floco is lichtgewicht. Voor assemblage-grafieken duurt het 8-22 minuten (peak memory < 3.1 GB). Voor complexere pangenoom-grafieken duurt het 40 minuten tot 3 uur (peak memory < 53 GB), wat aanzienlijk sneller is dan het aligneren van de reads zelf.

Betekenis en Conclusie

Floco biedt een robuuste en nauwkeurige oplossing voor het bepalen van kopieaantallen in de context van moderne genoom-grafieken. Door de topologie van de grafiek te gebruiken via netwerkstroom-optimalisatie, overwint de methode de beperkingen van lineaire referenties en de inconsistenties van lokale dekkingsschattingen.

Dit heeft belangrijke implicaties voor:

• Ziekte-associatie studies: Het nauwkeurig identificeren van CN-variatiën die geassocieerd zijn met fenotypes.
• Genoomassemblage: Het valideren en verbeteren van assemblage-grafieken door misassemblies te detecteren.
• Populatiegenetica: Het beter karakteriseren van complexe genomische variatie in pangenomen.

De tool is beschikbaar als open-source Python-code en is ontworpen om schaalbaar te zijn voor diverse grafiektypes, hoewel de prestaties afhankelijk blijven van de kwaliteit van de input-grafiek en de alignments.