ML-DSP: Machine Learning with Digital Signal Processing for ultrafast, accurate, and scalable genome classification at all taxonomic levels

Na het ontwerp en de implementatie van het ML-DSP genomic sequence classification tool prototype, hebben we onderzocht welk type van lengte-normalisatie en welk type van afstand het meest geschikt waren voor genoom classificatie met deze methode. Vervolgens hebben wij een uitgebreide analyse uitgevoerd van de verschillende numerieke representaties van DNA-sequenties die in de literatuur worden gebruikt, en hebben wij de top drie van de best presterende vastgesteld. Na het instellen van de belangrijkste parameters (lengte-normalisatie methode, afstand, en numerieke representatie), testten wij het vermogen van ML-DSP om mtDNA-genomen te classificeren op taxonomische niveaus variërend van het domein niveau tot aan het genus niveau, en verkregen gemiddelde niveaus van classificatie nauwkeurigheid van >97%. Tenslotte vergeleken we ML-DSP met andere alignment-gebaseerde en alignment-vrije genoom-classificatie methoden, en toonden aan dat ML-DSP een hogere nauwkeurigheid en significant hogere snelheden behaalde.

Analyse van afstanden en van lengte-normalisatie benaderingen

Om te beslissen welke afstandsmaat en welke lengte-normalisatie methode het meest geschikt waren voor genoom-vergelijkingen met ML-DSP, gebruikten we negen verschillende subsets van volledige mtDNA-sequenties uit onze dataset. Deze subsets werden geselecteerd om de meeste van de beschikbare volledige mtDNA genomen (Vertebraten dataset van 4322 mtDNA sequenties), evenals subsets die soortgelijke sequenties, van vergelijkbare lengte (Primaten dataset van 148 mtDNA sequenties), en subsets die mtDNA genomen met grote verschillen in lengte (Planten dataset van 174 mtDNA sequenties) te omvatten.

De classificatie nauwkeurigheid scores verkregen met behulp van de twee beschouwde afstand maatregelen (Euclidische en Pearson Correlatiecoëfficiënt) en twee verschillende lengte-normalisatie benaderingen (normalisatie op maximale lengte en normalisatie op mediane lengte) op verschillende datasets zijn vermeld in tabel 2. De scores voor classificatienauwkeurigheid zijn iets hoger voor PCC, maar liggen voldoende dicht bij die welke worden verkregen bij gebruik van de Euclidische afstand om geen uitsluitsel te geven.

In het vervolg van dit artikel hebben we gekozen voor de Pearson-correlatiecoëfficiënt omdat deze schaalonafhankelijk is (in tegenstelling tot de Euclidische afstand, die bijv, gevoelig is voor de offset van het signaal, waardoor signalen met dezelfde vorm maar verschillende beginpunten als ongelijksoortig worden beschouwd), en de lengte-normalisatie naar de mediaanlengte omdat deze zuinig is in termen van geheugengebruik.

Analyse van verschillende numerieke representaties van DNA-sequenties

We analyseerden het effect op de ML-DSP classificatienauwkeurigheid van dertien verschillende eendimensionale numerieke representaties voor DNA-sequenties, gegroepeerd als: Vaste mappings DNA numerieke representaties (Tabel 1 representaties #1, #2, #3, #6, #7, zie , en representaties #10, #11, #12, #13 – die eendimensionale varianten zijn van de binaire representatie voorgesteld in ), mappings gebaseerd op enkele fysio-chemische eigenschappen van nucleotiden (Tabel 1 representatie #4, zie , en representatie #5, zie ), en mappings gebaseerd op de nearest-neighbour waarden (Tabel 2 representaties #8, #9, zie ).

De datasets die voor deze analyse werden gebruikt, waren dezelfde als die in tabel 2. De classifiers voor machinaal leren met supervisie die voor deze analyse werden gebruikt, waren de zes classifiers die in het deel Methoden en uitvoering worden genoemd, met uitzondering van de datasets met meer dan 2000 sequenties, waarvoor twee van de classifiers (Subspace Discriminant en Subspace KNN) werden weggelaten omdat ze te traag waren. De resultaten en de gemiddelde nauwkeurigheidsscores voor al deze numerieke representaties, classificeerders en datasets zijn samengevat in Tabel 3.

Zoals uit tabel 3 blijkt, zijn voor alle numerieke representaties de tabelgemiddelde nauwkeurigheidsscores (laatste rij: gemiddelde van gemiddelden, eerst over de zes classifiers voor elke dataset, en dan over alle datasets), hoog. Verrassend genoeg levert zelfs het gebruik van een numerieke representatie van een enkele nucleotide, waarbij drie van de nucleotiden als gelijk worden behandeld, en slechts een ervan wordt uitgekozen (“Just-A”), een gemiddelde nauwkeurigheid van 91,9% op. De beste nauwkeurigheid, voor deze datasets, wordt bereikt bij gebruik van de “PP” representatie, die een gemiddelde nauwkeurigheid van 92.3% oplevert.

Voor latere experimenten selecteerden we de top drie representaties in termen van nauwkeurigheidsscores: “PP”, “Just-A”, en “Real” numerieke representaties.

ML-DSP voor drie klassen van vertebraten

Als een toepassing van ML-DSP met behulp van de “PP” numerieke representatie voor DNA-sequenties, analyseerden we de set van vertebrate mtDNA-genomen (mediane lengte 16.606 bp). De MoDMap, d.w.z. de multi-dimensionale schaling 3D visualisatie van de genoom interrelaties zoals beschreven door de afstanden in de afstandsmatrix, wordt geïllustreerd in Fig. 3. De dataset bevat 3740 volledige mtDNA-genomen: 553 vogel-genomen, 2313 vis-genomen, en 874 zoogdier-genomen. Kwantitatief bedroeg de classificatienauwkeurigheidsscore, verkregen door de kwadratische SVM-classificator, 100%.

Het classificeren van genomen met ML-DSP, op alle taxonomische niveaus

We testten het vermogen van ML-DSP om complete mtDNA sequenties op verschillende taxonomische niveaus te classificeren. Voor elke dataset testten we met behulp van de “PP”, “Just-A”, en “Real” numerieke representaties.

Het uitgangspunt was domein Eukaryota (7396 sequenties), dat werd geclassificeerd in koninkrijken, vervolgens werd koninkrijk Animalia geclassificeerd in fyla, enz. Op elk niveau kozen we de cluster met het hoogste aantal sequenties en deelden die in bij de volgende subclusters op taxonomisch niveau. Het laagste niveau dat werd geclassificeerd was dat van de familie Cyprinidae (81 sequenties) in zijn zes genera. Voor elke dataset hebben we alle zes classificeerders getest, en de maximale van deze zes classificatienauwkeurigheidsscores voor elke dataset zijn weergegeven in tabel 4.

Merk op dat, op elk taxonomisch niveau, de maximale classificatienauwkeurigheidsscores (van de zes classificeerders) voor elk van de drie beschouwde numerieke representaties hoog zijn, variërend van 91,4% tot 100%, met slechts drie scores (van de zes classificeerders) voor elk van de drie beschouwde numerieke representaties.4% tot 100%, met slechts drie scores onder 95%. Aangezien ook deze analyse geen duidelijke winnaar onder de drie beste numerieke representaties aan het licht bracht, rees de vraag of de numerieke representatie die we gebruiken er überhaupt toe doet. Om deze vraag te beantwoorden, hebben we twee extra experimenten uitgevoerd, die gebruik maken van het feit dat de Pearson correlatiecoëfficiënt schaalonafhankelijk is, en alleen naar een patroon zoekt bij het vergelijken van signalen. Voor het eerste experiment selecteerden we de top drie van numerieke representaties (“PP”, “Just-A”, en “Real”) en voor elke sequentie in een gegeven dataset werd willekeurig, met gelijke waarschijnlijkheid, een numerieke representatie onder deze drie gekozen als het digitale signaal dat de sequentie representeert. De resultaten staan vermeld in de kolom “Random3” in Tabel 4: De maximale nauwkeurigheidscore over alle datasets is 96%. Dit is bijna gelijk aan de nauwkeurigheid die werd verkregen wanneer één bepaalde numerieke weergave werd gebruikt (1% lager, hetgeen ruim binnen de experimentele fout ligt). Vervolgens hebben we dit experiment herhaald, ditmaal met een willekeurige keuze uit een van de dertien beschouwde numerieke voorstellingen. De resultaten staan in de kolom “Random13” in Tabel 4, met een tabel als gemiddelde nauwkeurigheidsscore van 88,1%.

In het algemeen suggereren onze resultaten dat alle drie numerieke representaties “PP”, “Just-A”, en “Real” zeer hoge classificatienauwkeurigheidsscores hebben (gemiddeld >97%), en zelfs een willekeurige keuze van een van deze representaties voor elke sequentie in de dataset heeft geen significante invloed op de classificatienauwkeurigheidsscore van ML-DSP (gemiddeld 96%).

We merken ook op dat, naast het feit dat ML-DSP zeer nauwkeurig is in zijn classificaties, het ook supersnel is. Inderdaad, zelfs voor de grootste dataset in tabel 2, subphylum Vertebrata (4322 complete mtDNA-genomen, gemiddelde lengte 16.806 bp), de afstand matrix berekening (dat is het grootste deel van de classificatie berekening) duurde minder dan 5 s. Het classificeren van een nieuw primaten mtDNA-genoom duurde 0,06 s wanneer getraind was op 148 primaten mtDNA-genomen, en het classificeren van een nieuw gewerveld mtDNA-genoom duurde 7 s wanneer getraind was op de 4322 vertebraten mtDNA-genomen. Het resultaat werd bijgewerkt met een experiment waarbij QSVM werd getraind op de 4322 volledige vertebrate genomen in tabel 2, en gequerried op de 694 nieuwe vertebrate mtDNA-genomen geüpload op NCBI tussen 17 juni 2017 en 7 januari 2019. De nauwkeurigheid van de classificatie was 99,6%, met slechts drie reptielen mtDNA-genomen verkeerd geclassificeerd als amfibieëngenomen: Bavayia robusta, robust forest bavayia – een soort gekko, NC_034780, Mesoclemmys hogei, Hoge’s toadhead turtle, NC_036346, en Gonatodes albogularis, yellow-headed gecko, NC_035153.

MoDMap visualisatie vs. ML-DSP kwantitatieve classificatie resultaten

De hypothese getest door de volgende experimenten was dat de kwantitatieve nauwkeurigheid van de classificatie van DNA-sequenties door ML-DSP significant hoger zou zijn dan gesuggereerd door de visuele clustering van taxa in de MoDMap geproduceerd met dezelfde paarsgewijze afstand matrix.

Als voorbeeld, de MoDMap in Fig. 4a, visualiseert de afstandsmatrix van mtDNA-genomen van de familie Cyprinidae (81 genomen) met de genera Acheilognathus (10 genomen), Rhodeus (11 genomen), Schizothorax (19 genomen), Labeo (19 genomen), Acrossocheilus (12 genomen), Onychostoma (10 genomen); alleen de genera met ten minste 10 genomen zijn in aanmerking genomen. De MoDMap lijkt te wijzen op een overlapping tussen de clusters Acheilognathus en Rhodeus, wat biologisch plausibel is, aangezien deze genera tot dezelfde subfamilie Acheilognathinae behoren. Wanneer echter wordt ingezoomd door het plotten van een MoDMap van alleen deze twee genera, zoals getoond in Fig. 4b, kan men zien dat de clusters visueel duidelijk gescheiden zijn. Deze scheiding wordt bevestigd door het feit dat de nauwkeurigheidsscore van de Kwadratische SVM classificator voor de dataset in Fig. 4b 100% is. Dezelfde kwantitatieve nauwkeurigheidsscore voor de classificatie van de dataset in Fig. 4a met Kwadratische SVM is 91,8%, wat intuïtief veel beter is dan de overeenkomstige MoDMap zou suggereren. Dit is waarschijnlijk te wijten aan het feit dat de MoDMap een driedimensionale benadering is van de posities van de genoom-representerende punten in een multidimensionale ruimte (het aantal dimensies is (n-1), waarbij n het aantal sequenties is).

Dit gezegd zijnde, kunnen MoDMaps nog steeds dienen voor exploratieve doeleinden. Bijvoorbeeld, de MoDMap in Fig. 4a suggereert dat soorten van het genus Onychostoma (subfamilie “onbekend” in NCBI) (geel), genetisch verwant kunnen zijn met soorten van het genus Acrossocheilus (subfamilie Barbinae) (magenta). Bij nadere bestudering van de afstandsmatrix blijkt dat de afstand tussen de centroïden van deze twee clusters inderdaad kleiner is dan de afstand tussen elk van deze twee cluster-centroïden en de andere cluster-centroïden. Dit ondersteunt de hypothesen, gebaseerd op morfologisch bewijs, dat het genus Onychostoma behoort tot de subfamilie Barbinae, respectievelijk dat het genus Onychostoma en het genus Acrossocheilus nauw verwant zijn. Merk op dat deze exploratie, gesuggereerd door MoDMap en bevestigd door berekeningen op basis van de afstandsmatrix, niet had kunnen worden gestart op basis van ML-DSP alleen (of andere gesuperviseerde machine learning algoritmen), omdat ML-DSP alleen de classificatie van nieuwe genomen voorspelt in een van de taxa waarop het werd getraind, en geen andere aanvullende informatie levert.

Als een ander vergelijkingspunt tussen MoDMaps en supervised machine learning outputs, toont Fig. 5a de MoDMap van de superorde Ostariophysi met de orden Cypriniformes (643 genomen), Characiformes (31 genomen) en Siluriformes (107 genomen). De MoDMap toont de clusters als overlappend, maar de Quadratic SVM classificator die deze genomen kwantitatief classificeert heeft een nauwkeurigheid van 99%. De verwarringsmatrix in fig. 5b laat zien dat de Kwadratische SVM slechts 8 van de 781 sequenties verkeerd classificeert (voor m clusters zijn de rijen van de m×m verwarringsmatrix gelabeld met de ware klassen en de kolommen met de voorspelde klassen; de cel (i,j) toont het aantal sequenties dat tot de ware klasse i behoort en waarvan voorspeld is dat ze tot klasse j behoren). Dit geeft aan dat wanneer de visuele weergave in een MoDMap clusteroverlappingen vertoont, dit wellicht alleen het gevolg is van de dimensionaliteitsreductie tot drie dimensies, terwijl ML-DSP in feite een veel betere kwantitatieve classificatie oplevert op basis van dezelfde afstandsmatrix.

Toepassingen op andere genomic datasets

De twee experimenten in deze sectie geven aan dat de toepasbaarheid van onze methode is niet beperkt tot mitochondriale DNA-sequenties. Het eerste experiment, Fig. 6a, toont de MoDMap van alle 4721 complete dengue virus sequenties beschikbaar in NCBI op 10 augustus 2017, ingedeeld in de subtypen DENV-1 (2008 genomen), DENV-2 (1349 genomen), DENV-3 (1010 genomen), DENV-4 (354 genomen). De gemiddelde lengte van deze volledige virale genomen is 10.595 bp. Hoewel de dengue virale genomen zeer vergelijkbaar zijn, was de classificatienauwkeurigheid van deze dataset in subtypes, met behulp van de Quadratic SVM classifier, 100%. Het tweede experiment, Fig. 6b, toont de MoDMap van 4710 bacteriële genomen, ingedeeld in drie fyla: Spirochaetes (437 genomen), Firmicutes (1129 genomen), en Proteobacteria (3144 genomen). De gemiddelde lengte van deze volledige bacteriële genomen is 104.150 bp, met een maximumlengte van 499.136 bp en een minimumlengte van 20.019 bp. De classificatienauwkeurigheid van de kwadratische SVM-classificator voor deze dataset bedroeg 95,5%.

Vergelijking van ML-DSP met state-of-the-art alignment-gebaseerde en alignment-vrije tools

De computationele experimenten in deze sectie vergelijken ML-DSP met drie state-of-the-art alignment-gebaseerde en alignment-vrije methoden: het alignment-gebaseerde tool MEGA7 met alignment met behulp van MUSCLE en CLUSTALW , en de alignment-vrije methode FFP (Feature Frequency Profiles) .

Voor deze prestatie-analyse hebben wij drie datasets geselecteerd. De eerste twee datasets zijn benchmark datasets gebruikt in andere genetische sequentie vergelijking studies : De eerste dataset omvat 38 influenza virale genomen, en de tweede dataset bestaat uit 41 zoogdieren volledige mtDNA-sequenties. De derde dataset, van onze keuze, is veel groter, bestaande uit 4.322 vertebrate volledige mtDNA sequenties, en werd geselecteerd om de schaalbaarheid te vergelijken.

Voor de alignment-gebaseerde methoden, gebruikten we de afstand matrix berekend in MEGA7 van sequenties uitgelijnd met ofwel MUSCLE of CLUSTALW. Voor de uitlijningsvrije FFP gebruikten we de standaardwaarde van k=5 voor k-mers (een k-mer is elke DNA-sequentie met lengte k; elke verhoging van de waarde van de parameter k, voor de eerste dataset, resulteerde in een lagere classificatienauwkeurigheidsscore voor FFP). Voor ML-DSP kozen we de Integer numerieke representatie en berekenden we de gemiddelde classificatienauwkeurigheid over alle zes classifiers voor de eerste twee datasets, en over alle classifiers behalve Subspace Discriminant en Subspace KNN voor de derde dataset.

Tabel 5 toont de prestatievergelijking (classificatienauwkeurigheid en verwerkingstijd) van deze vier methoden. De verwerkingstijd omvatte alle berekeningen, vanaf het lezen van de datasets tot de voltooiing van de afstandsmatrix – het gemeenschappelijke element van alle vier methoden. De aangegeven verwerkingstijden omvatten niet de tijd die nodig is voor de berekening van fylogenetische bomen, MoDMap-visualisaties, of classificatie.

Zoals te zien is in tabel 5 (kolommen 3, 4 en 6) presteert ML-DSP qua verwerkingstijd overweldigend beter dan de op alignment gebaseerde software MEGA7(MUSCLE/CLUSTALW). Wat de nauwkeurigheid betreft, voor de kleinere virus en zoogdier benchmark datasets, waren de gemiddelde nauwkeurigheden van ML-DSP en MEGA7(MUSCLE/CLUSTALW) vergelijkbaar, waarschijnlijk door de kleine omvang van de training set voor ML-DSP. Het voordeel van ML-DSP boven de alignment-gebaseerde tools werd duidelijker voor de grotere vertebrate dataset, waar de nauwkeurigheden van ML-DSP en de alignment-gebaseerde tools niet eens vergeleken konden worden, omdat de alignment-gebaseerde tools zo traag waren dat ze moesten worden stopgezet. ML-DSP daarentegen classificeerde de gehele set van 4322 vertebrate mtDNA genomen in 28 s, met een gemiddelde classificatienauwkeurigheid van 98.3%. Dit geeft aan dat ML-DSP aanzienlijk schaalbaarder is dan de alignment-gebaseerde MEGA7(MUSCLE/CLUSTALW), omdat het snel en accuraat datasets kan classificeren die alignment-gebaseerde tools niet eens kunnen verwerken.

Zoals te zien in Tabel 5 (kolommen 5 en 6), presteert ML-DSP significant beter dan de alignment-vrije software FFP in termen van nauwkeurigheid (gemiddelde classificatienauwkeurigheid 98.3% voor ML-DSP vs. 48,3% voor FFP, voor de grote gewervelde dataset), terwijl ze tegelijkertijd in het algemeen sneller zijn.

Deze vergelijking geeft ook aan dat, voor deze datasets, beide alignment-vrije methoden (ML-DSP en FFP) een overweldigend voordeel hebben boven de alignment-gebaseerde methoden (MEGA7 (MUSCLE/CLUSTALW)) in termen van verwerkingstijd. Bovendien, wanneer de twee alignment-vrije methoden met elkaar worden vergeleken, overtreft ML-DSP significant FFP in termen van classificatienauwkeurigheid.

Als een andere hoek van vergelijking, toont Fig. 7 de MoDMaps van de eerste benchmark dataset (38 influenza virus genomen) geproduceerd uit de afstandsmatrices gegenereerd door respectievelijk FFP, MEGA7 (MUSCLE), MEGA7 (CLUSTALW), en ML-DSP. Figuur 7a laat zien dat het met FFP moeilijk is om een visuele scheiding van de dataset in subtype clusters waar te nemen. Figuur 7b, MEGA7 (MUSCLE), en Fig. 7c MEGA7 (CLUSTALW) tonen overlappingen van de clusters van punten die de subtypes H1N1 en H2N2 vertegenwoordigen. Fig. 7d, waarin de door ML-DSP geproduceerde afstandsmatrix wordt gevisualiseerd, laat daarentegen een duidelijke scheiding tussen alle subtypen zien.

Figuren tenslotte Fig. Figuur 8 en 9 tonen de fylogenetische bomen gegenereerd door elk van de vier methoden in kwestie. Figuur 8a, de boom gegenereerd door FFP, heeft veel verkeerd geclassificeerde genomen, die werd verwacht gezien de MoDMap visualisatie van de afstand matrix in Fig. 7a. Figuur 9a toont de fylogenetische boom gegenereerd door MEGA7, die hetzelfde was voor zowel MUSCLE als CLUSTALW: Het heeft slechts één foutief geclassificeerd H5N1 genoom, geplaatst in het midden van H1N1 genomen. Figuren 8b en 9b tonen de fylogenetische boom die is gegenereerd met behulp van de door ML-DSP geproduceerde afstand (tweemaal weergegeven, parallel met de andere bomen, voor het gemak van vergelijking). ML-DSP classificeerde alle genomen correct.

Discussie

De computationele efficiëntie van ML-DSP is te danken aan het feit dat het alignment-vrij is (er is dus geen multiple sequence alignment nodig), terwijl de combinatie van 1D numerieke representaties, Discrete Fourier Transform en Pearson Correlation Coefficient het uiterst computationeel tijdsefficiënt maakt, en dus schaalbaar.

ML-DSP is niet zonder beperkingen. We verwachten dat de noodzaak voor gelijke lengte sequenties en het gebruik van de lengte normalisatie zou kunnen problemen introduceren met het onderzoek van kleine fragmenten van grotere genoom sequenties. Gewoonlijk variëren genomen in lengte en dus resulteert lengtenormalisatie altijd in het toevoegen (up-sampling) of verliezen (down-sampling) van enige informatie. Hoewel de Pearson Correlatie Coëfficiënt de signaalpatronen zelfs in kleine sequentie fragmenten kan onderscheiden, en we geen aanzienlijk nadeel vonden bij het beschouwen van volledige mitochondriale DNA-genomen met hun onvermijdelijke lengte variaties, kan lengte normalisatie problemen veroorzaken wanneer we te maken hebben met de fragmenten van genomen, en de veel grotere nucleaire genoom sequenties.

Ten slotte heeft ML-DSP twee nadelen, inherent aan elk gesuperviseerd machine-learning algoritme. De eerste is dat ML-DSP een black-box methode is die weliswaar een zeer nauwkeurige classificatievoorspelling oplevert, maar geen (biologische) verklaring biedt voor zijn output. De tweede is dat zij afhankelijk is van het bestaan van een trainingsset waaruit zij haar “kennis” put, d.w.z. een set bestaande uit bekende genomische sequenties en hun taxonomische labels. ML-DSP gebruikt zo’n trainingsset om te “leren” nieuwe sequenties in te delen in één van de taxonomische klassen waarop het getraind is, maar het is niet in staat deze toe te wijzen aan een taxon waaraan het niet is blootgesteld.