Similarity analysis of DNA sequences through local distribution of nucleotides in strategic neighborhoods

Technische Samenvatting: Gelijkenis-analyse van DNA-sequenties door lokale distributie van nucleotiden in strategische buurten

Probleemstelling
De snelle expansie van biologische databases heeft de noodzaak voor efficiënte computationele instrumenten voor de analyse van DNA-sequenties vergroot. Hoewel traditionele alignment-gebaseerde algoritmen (bijv. Needleman-Wunsch, Smith-Waterman, BLAST) nauwkeurigheid bieden, vertonen zij doorgaans een kwadratische tijdscomplexiteit, wat computationeel onhaalbaar wordt voor lange sequenties of grootschalige vergelijkende genomica. Hoewel alignment-vrije (AF) algoritmen zijn voortgekomen als een lineaire-tijd alternatief, blijft er behoefte aan methoden die compacte representaties, laag geheugengebruik en robuustheid bieden bij het afhandelen van sequenties van ongelijke lengtes zonder uitsluitend te vertrouwen op specifieke woordfrequentiecategorieën of informatie-theoretische metrieken.

Methodologie
De auteurs stellen een nieuw alignment-vrij algoritme voor genaamd PPN (Prime Factorization Neighborhood). De kernmethodologie omvat het construeren van een compacte vectorrepresentatie van een DNA-sequentie in een 24-dimensionale reële Euclidische ruimte ($\mathbb{R}^{24}$). Het proces is als volgt gedefinieerd:

1. Prime Mapping en Permutaties: De vier nucleotiden (A, C, G, T) worden gemapt naar de eerste vier priemgetallen $\{2, 3, 5, 7\}$. Om geen bias naar een specifieke ordening te garanderen, beschouwen de auteurs alle $4! = 24$ permutaties ($\sigma_0$ tot $\sigma_{23}$) van deze priemgetallen.
2. Strategische Buurten: Voor een DNA-sequentie $\xi$ met lengte $N$, definieert het algoritme "buurten" $U_l(s_i)$ met een specifieke straal $l$ gecentreerd rond strategische posities. De afstand $t$ tussen de centra van opeenvolgende buurten is een instelbare parameter. Om informatieve continuïteit te behouden, wordt $t$ beperkt zodat $1 \le t \le l$, wat overlappende buurten garandeert.
3. Compacte Representatie via Priemfactorisatie: Voor elke buurt berekent een functie $\Gamma$ een unieke integerwaarde op basis van de frequenties ($f_1, f_2, f_3, f_4$) van de nucleotiden binnen die buurt. De waarde wordt berekend als het product van de toegewezen priemgetallen verheven tot de macht van hun respectieve frequenties:
   $$\Gamma_j(U_l(s_i)) = [\sigma_j(1)]^{f_1} \cdot [\sigma_j(2)]^{f_2} \cdot [\sigma_j(3)]^{f_3} \cdot [\sigma_j(4)]^{f_4}$$
   Vanwege de uniciteit van priemfactorisatie codeert deze integer de volledige lokale distributie van nucleotidefrequenties volledig.
4. Vectorconstructie: Een sequentie $\zeta$ wordt gevormd door de $\Gamma$-waarden op intervallen van $t$ te verzamelen. De lengte van $\zeta$ is ongeveer $N/2$ (of kleiner), wat zorgt voor een "grofmazige" compacte representatie.
5. Scalaire en Metrische Berekening: Voor elke permutatie wordt een scalaire $\eta_j$ afgeleid door de elementen van $\zeta$ op te tellen. Dit resulteert in een representatieve vector $\vec{\eta} = (\eta_0, \dots, \eta_{23})$. De gelijkenis tussen twee DNA-sequenties wordt bepaald door de Euclidische afstand ($\rho$) tussen hun respectieve vectoren te berekenen.

Belangrijkste Bijdragen

• Nieuwe Representatie: Het artikel introduceert een methode die een DNA-sequentie omzet in een 24-dimensionale vector met behulp van de priemfactorisatie van lokale nucleotidefrequenties, wat een wiskundig rigoureuze manier biedt om de lokale distributie zonder alignment te coderen.
• Compactheid en Efficiëntie: Door buurten te samplen op intervallen ($t$) in plaats van bij elke nucleotide, reduceert de methode de datagrootte aanzienlijk (ongeveer met de helft), wat leidt tot een algoritme met lineaire tijdscomplexiteit.
• Parameteroptimalisatie: De auteurs hebben empirisch de optimale parameters ($l=4, t=1$) bepaald door de gegenereerde fylogenetische bomen van PPN te vergelijken met benchmark-datasets (vis mtDNA), waarbij de genormaliseerde Robinson-Foulds (nRF) en de genormaliseerde Quartet Distance (nQD) werden geminimaliseerd.
• Robuustheid tegen Lengteverschillen: De scalaire constructie maakt het mogelijk om sequenties met zeer verschillende lengtes te vergelijken, een veelvoorkomend probleem in de genomische analyse.

Resultaten

• Fylogenetische Nauwkeurigheid: Bij toepassing op vis mtDNA-datasets produceerde het PPN-algoritme een fylogenetische boom met een nRF-afstand van 0,64 en een nQD van 0,2602 vergeleken met de benchmark. De methode werd ook succesvol toegepast voor het genereren van fylogenetische bomen voor zoogdieren (41 soorten) en diverse bacteriële stammen (E. Coli/Shigella, Yersinia).
• Computationele Prestaties:
  • Runtime: In tests op vijf complete genoomsequenties (Zoogdieren, Influenza, Rhino, Ebola, Corona) toonde PPN concurrerende of superieure snelheden aan vergeleken met CD-MAWS en Co-phylog. Bijvoorbeeld, op de Zoogdieren-dataset nam PPN 0,052 minuten in beslag versus 0,151 minuten voor Co-phylog.
  • Schaalbaarheid: Op gesimuleerde datasets variërend van 100 tot 900 soorten (elk met 50.000 nucleotiden) behield PPN lagere gemiddelde looptijden en piekgeheugengebruik vergeleken met de twee benchmark AF-algoritmen.
  • Afhandeling van Grote Schaal: Het algoritme verwerkte succesvol een vergelijking tussen een Zea mays chromosoom (30,7 miljoen nucleotiden) en een Oryza sativa chromosoom (4,3 miljoen nucleotiden), waarbij de afstandsberekening in 33,68 minuten werd voltooid met een piekgeheugengebruik van 20,24 GB op een standaard serverconfiguratie.

Betekenis en Claims
De auteurs beweren dat het PPN-algoritme computationeel efficiënt is, waarbij het een lineaire tijdscomplexiteit vertoont en aanzienlijk lager geheugengebruik heeft dan bestaande bekende alignment-vrije tools. Het vermogen van de methode om een "compacte" representatie te genereren, reduceert de praktische looptijd terwijl de lokale distributie-informatie van nucleotiden behouden blijft door de wiskundige uniciteit van priemfactorisatie.

Het artikel stelt dat deze efficiëntie de methode toegankelijk maakt voor een bredere groep onderzoekers die mogelijk niet beschikken over high-performance computing-resources. Bovendien suggereren de auteurs dat de door PPN gegenereerde vectorrepresentatie geschikt is voor feature extractie in machine learning-modellen. De studie concludeert dat de methode effectief het probleem van het vergelijken van sequenties van ongelijke lengte omzeilt en een snelle, geheugenefficiënte alternatief biedt voor grootschalige genomische gelijkenis-analyse.