A Short -Read Sequence Mapping ( angolul Short-Read Sequence Alignment, Short-Read Sequence Mapping ) egy bioinformatikai módszer a második generációs szekvenálás eredményeinek elemzésére , amely abból áll, hogy meghatározzák azokat a pozíciókat a referencia genomban vagy transzkriptomban, ahonnan az egyes rövid leolvasások kiindulhatnak. a legnagyobb valószínűséggel kapjuk meg. Általában az adatfeldolgozás első lépése, ha a vizsgált organizmus genomja ismert.
A következő generációs szekvenáló platformok több millió rövid, 50-500 bp hosszúságú szekvencia hatékony szekvenálását teszik lehetővé. Ehhez a DNS- vagy cDNS - molekulát sok rövid szegmensre osztják, amelyeket azután párhuzamosan szekvenálnak. Ezeknek a rövid szegmenseknek a szekvenált szekvenciáinak (leolvasások) beszerzése után a teljes genomot vagy cDNS-szekvenciák készletét kell rekonstruálni belőlük. Ehhez minden leolvasáshoz meg kell határozni a referenciagenom legvalószínűbb pozícióját.
Ellentétben a de novo reassembly-vel , amely összegyűjti a leolvasásokat, hogy rekonstruálják ezt az ismeretlen genomot, sok jelenlegi projektnek van "referenciagenomja" – egy másik szervezetből származó, már ismert közeli genom. Vagy lehet referencia sorozatok halmaza. Ebben az esetben ahhoz, hogy az olvasmány valamilyen jelentést adjon, meg kell határozni a referenciaadatokban elfoglalt helyét. Ezt a folyamatot leképezésnek vagy igazításnak nevezik . A térképezés a különböző feladatoknál némileg eltérő megjelenésű lehet, például: a genomikus térképezésnél a nagy rések hiányoznak, míg az RNS-seq esetében a splicing jelenléte miatt megengedettek. Általánosságban elmondható, hogy a leképezési feladatok nem változtak a szekvenszerek utolsó generációja óta, de az előző generációhoz kifejlesztett programokat nem úgy tervezték, hogy megnövelt adatmennyiséggel működjenek, és nem működnek jól rövid hosszúságú leolvasásokkal.
A fő probléma az, hogy a vizsgált genom a genom variabilitása miatt (például SNP -k vagy indelek miatt), valamint szekvenálási hibák miatt eltér a referenciagenomtól. Emiatt a leolvasás és annak „helyes” pozíciója a referenciagenomban jobban eltérhet, mint ennek a régiónak a referenciagenom bármely más helyéhez való igazítása, ezért a térképező programoknak képesnek kell lenniük pontatlan egyezések megtalálására. Ehhez különféle heurisztikákat használnak. Ha ezt az RNS-seq esetében a splicing lehetőségével vetjük rá, a probléma még bonyolultabbá válik.
Problémát jelentenek az ismétlődő elemekhez tartozó olvasások is. Ebben az esetben nem mindig lehet egyértelműen eldönteni, hogy hol kell ezt az olvasatot feltérképezni. Egy ilyen szekvencia véletlenszerűen leképezhető bármely megfelelő helyre, vagy megjelölhető úgy, hogy több helyre van leképezve.
Ha a referenciagenom nagy, és több milliárd leolvasás történt, akkor a feltérképezési idő nagy probléma. Az igazítás mindig is rendkívül erőforrás-igényes feladat volt, de ebben az esetben a probléma minőségileg új szintre lép, rendkívüli racionalitást, valamint a processzoridő és a memória hatékony kihasználását követeli meg az algoritmusoktól.
E problémák megoldásának két fő megközelítése van: hash táblák és utótagfák vagy tömbök használata.
A hash-t használó keresési folyamat sokszor gyorsabb és olcsóbb, mint a Smith-Waterman algoritmus dinamikus programozásával végzett klasszikus igazítás .
Ez a megközelítés hash függvényt használ, amely lehetővé teszi, hogy egy karakterláncot olyan kulccsá alakítson át, amely gyors keresésekhez használható. A legegyszerűbb módja az lenne, ha a genomot olyan szavakra osztanák, amelyek megfelelnek az olvasás hosszának, de ez a megközelítés nem működik, mivel a hosszú szavak nagyobb valószínűséggel egyediek, és tárolásuk túl sok memóriaterületet foglalna el. Ehelyett a rövidebb szakaszok kivonatolását használják, amelyek sokkal gyakoribbak. Miután a hash függvény megfelelő pozíciókat kapott, megpróbálhatjuk a leolvasás hátralévő részét a genomra leképezni. Ezenkívül az olvasás több részre osztása lehetővé teszi a helyettesítések lehetőségét az algoritmusba. Tehát a Maq programban a leolvasás 4 részre van osztva, úgynevezett seedekre (rövid szakaszok pontos egyezésekkel). Ha a leolvasás tökéletesen illeszkedik a referenciához, akkor mind a 4 mag tökéletesen illeszkedik. Ha van egy eltérés az olvasásban, ami valószínűleg SNP -k jelenléte vagy szekvenálási hibák miatt következik be, akkor az egyik magba kerül, míg a másik 3 továbbra is tökéletesen leképez. Hasonlóképpen, két cserével legalább két mag tökéletesen illeszkedik. Így az összes lehetséges olvasáspár indexeléssel történő feltérképezésével (6 db lesz, hiszen a magoknak meghatározott sorrendben kell menniük) a genomban korlátozott számú helyet kapunk, ahol a teljes leolvasás leképezhető, miután amely a szokásos igazítással meghatározható, hogy melyik pozíció illeszkedik a legjobban (lásd az 1a képet). A SOAP, az RMAP és a SeqMap hasonlóan működik.
Ennek a megközelítésnek a módosítása lehet az az ötlet, hogy az olvasás összes k-mértékét figyelembe vegyük, ahelyett, hogy egy bizonyos hosszúságú szakaszok nem átfedőek. Tehát az ACGT olvasásához 3 lesz belőle: AC, CG, GT. A SHRiMP2 és a RazerS hasonló módon működik. Ez növeli az érzékenységet, de növeli az időköltséget is.
Mindezek az információk sok memóriát foglalnak el. A felhasznált memória mennyiségének csökkentése érdekében a legtöbb program a nukleotidok kétbites kódolását használja (A 00, C 01, G 10, T 11), de ez nem teszi lehetővé a kétértelmű N nukleotid használatát, amely mind az olvasásban, mind az olvasásban jelen lehet. a referencia genomban. A programok különböző megközelítéseket alkalmaznak ennek megkerülésére. Tehát a BWA az N-t véletlenszerű nukleotiddal helyettesíti, a SOAP2 pedig az összes N-t G-re cseréli.
Különféle fejlesztések használhatók az algoritmusok felgyorsítására és a hibák kikerülésére. Például használjunk közömbös pozíciókat (jelöljük X-szel). Így az ACGxACG seed az ACGAACG-n és az ACGCACG-n is igazodik, ami növeli a leképezés érzékenységét (bár ez növeli a feldolgozási időt, mivel minden leolvasáshoz több lelet lesz). Ezt olyan programokban használják, mint a Zoom, BFAST, GASSST, SHRiMP2, PerM.
Az algoritmusok legtöbbször nem magok keresésével, hanem környezetük ellenőrzésével töltik. A legtöbb program a Needleman-Wunsch algoritmust vagy annak módosításait használja. Mások, például a GASSST, hozzáadnak egy közbenső lépést az Euler-távolság méréséhez, amely egyszerűen figyelembe veszi az azonos betűk számát. Például, ha egy 5 G-t tartalmazó olvasást próbálunk leképezni egy csak 1 G-t tartalmazó régióra, akkor legalább 4 cserénk lesz. Ez a megközelítés lehetővé teszi a nem megfelelő területek gyors kiszűrését és pontosabb (de költséges) megközelítések alkalmazását csak az ígéretes régiókban.
Nem a genomot lehet kivonatolni és olvasmányokat keresni benne, hanem az olvasmányokat kivonatolni és a genom azonos hosszúságú szakaszait keresni bennük. A Maq, az Rmap és a SeqMap korai verziói ezt a megközelítést alkalmazták, de azóta egy kísérletben az olvasások száma jelentősen megnőtt, és ez a megközelítés megszűnt racionálisnak lenni.
A hashelésen alapuló algoritmusok nem bírják jól az ismétlődéseket, mivel jelentősen megnő az ellenőrizendő magok száma. Ennek megoldására utótagfákon és utótagtömbökön alapuló algoritmusokat használnak . Ennek a megközelítésnek az az előnye, hogy az ismétlések nem növelik az algoritmus futási idejét, mivel az ismétlődő szakaszok "összeesnek" az utótagfában. A legtisztább formájában ez a megközelítés rendkívül gyorsan működik, feltéve, hogy nincsenek hibák és cserék (például az MPscan program használja).
Az utótag tömb több memória megtakarítására szolgál. Általánosságban elmondható, hogy az utótagtömbön keresztüli keresés alapvetően nem különbözik az utótagfával való munkavégzéstől, de kissé összetettebb megközelítést igényel. A Burroughs-Wheeler transzformációt gyakran használják . Az összes transzformáció után egy ilyen utótag tömb mérete összemérhető az eredeti genom méretével. Tehát a teljes emberi genomra nézve a csokornyakkendő-program által létrehozott utótag-tömb 2 gigabájtot foglal el. Összehasonlításképpen: egy hash-alapú indexek adatbázisa (mint a Maq programban használt) körülbelül 50 gigabájt memóriát foglal el.
A Ferragin-Manizi algoritmust a szavak keresésére használják .
Egyszerűsített formában a folyamat a következő. A leolvasások egy nukleotidot igazítanak a Burrows-Wheeler-transzformált genomhoz. Minden egyes igazított nukleotid lehetővé teszi a program számára, hogy szűkítse azon helyek számát, ahová a teljes leolvasás eljuthat. Ha a program nem talál olyan pozíciót, ahol a leolvasás tökéletesen illeszkedik, akkor visszatér az előző lépéshez, cserét hajt végre és folytatja a keresést. Így működik például a SHRiMP. Másrészt, ha a megengedett hibák száma nagy, akkor ez lassítani kezdi az algoritmust. Egy kicsit érdekesebb módosítást használnak a BWA programban – először az olvasás bal és jobb oldalát igazítja, feltételezve, hogy e két régió közül legalább az egyikben kevesebb lesz a hiba (ami azon a tényen alapul, hogy az 5' vége általában jobb sorrendben).
Jelenleg mind az egyik, mind a másik megközelítést alkalmazó programok vannak. Annak ellenére, hogy a Burroughs-Wheeler transzformáción alapuló programok egyre népszerűbbek, nem mondható, hogy ez a megközelítés jobb lenne. Ezek a programok gyorsabban és jobban kezelik az ismétlődéseket, mint a hash alapú programok, de kisebb valószínűséggel kezelik a hibákat. A második típusú programok esetében az ellenkező helyzet figyelhető meg: a hashelés lehetővé teszi a hibák jó elszámolását, de az ismétlődések esetén sok időt vesz igénybe.
Ebben az esetben az összeillesztés lehetőségét is figyelembe kell venni. Alapvetően a már ismert exonokra és intronokra vonatkozó ismereteket használják fel, amelyek lehetővé teszik egy exon-exon asszociációkból álló adatbázis létrehozását, és már azon hagyományos algoritmusok, például bowtie vagy maq megvalósítását. Nyilvánvaló, hogy ez a megközelítés nem veszi figyelembe a korábban ismeretlen intronokat, így kombinálható a gépi tanulással az ismeretlen splicingek előrejelzésére.
Előfordulhat, hogy egy másik megközelítés egyáltalán nem használja a megjegyzést. Az annotáció nélküli működési módban a TopHat először meghatározza a potenciális exonokat, ezen információk alapján adatbázist készít a lehetséges splicing helyekről, majd ennek segítségével leképezi a leolvasásokat. A potenciális exonokat a szomszédos RNS-seq leolvasások helye határozza meg, amikor a genomhoz igazodnak. Mivel sok exon rövidebb, mint a jelenlegi olvasási szekvenátorok által generált exonok, a kezdeti leképezési fázisban nem észlelhetők. A TopHat ezt a problémát főleg úgy oldja meg, hogy az olvasást rövidebb darabokra bontja és egymástól függetlenül leképezi.
A TopHat két fő módszert használ a lehetséges illesztési helyek azonosítására. Az első és fő tényező a potenciális splicing hely mellett az, ha egy leolvasás két szegmense (45 bázispár vagy annál hosszabb leolvasások esetén) egymástól bizonyos távolságra van leképezve, vagy ha az olvasás belső szegmense nem sikerül. feltérképezve. Egy másik tényező a "lefedési szigetek" párok megjelenése, amelyek olyan helyek, ahol sok RNS-seq leolvasás van egymás mellett leképezve. A szomszédos szigetek gyakran össze vannak vágva, és egymás mellett helyezkednek el az átiratban, ezért a TopHat keresi a módját, hogyan kapcsolja össze őket egy intron segítségével.
Az annotáció alapú algoritmusokkal a fő probléma az, hogy nagymértékben függenek maguknak az annotációk minőségétől, míg a gépi tanulást használó algoritmusok nagymértékben függenek a betanító halmaz minőségétől. Sőt, tekintettel arra, hogy az új megjegyzések a régieken alapulnak, az annotációk hibái „elterjedhetnek”, egyre „jelentősebbé” válnak, és sokkal nehezebben észlelhetők.
Rövidítés az angolból. Blat-szerű gyors, pontos keresőeszköz . A program fejlesztői a program hibákra, SNP -kre és indelekre való érzékenységére összpontosítottak, lehetővé téve a sebesség és a pontosság közötti egyensúly kiválasztását.
Támogatja a páros végű szekvenálást . A végső igazításhoz a Smith-Waterman algoritmust használja , támogatja a hézagokat és a kis indelek meghatározását [1] . Képes párhuzamos üzemmódban dolgozni egy klaszteren. A bfast+bwa programnak van egy verziója. Támogatja az Illumina, ABI SOLiD, 454, Helicos adatformátumokat.
BLAST-szerű beállító eszköz. Sebességre optimalizálva a nem átfedő K-töredékek indexének használatával, amely illeszkedik a számítógép RAM-jába [2] .
Mérkőzésenként egy cserét tesz lehetővé.
A Burrows-Wheeler algoritmust használja az indexeléshez. A program sebességre és memóriafogyasztásra van optimalizálva, több processzormagot is tud használni. A deklarált sebesség azonos feltételek mellett meghaladja a MAQ sebességének 35-szörösét és a SOAP sebességének 300-szorosát. [3]
Lehetővé teszi az eltéréseket.
A Bowtie alapján készült a TopHat program az RNS-seq leolvasások összehangolására.
A BWA (Biological Sequence Alignment) három programból áll: BWA-backtrack, BWA-SW és BWA-MEM. A BWA-backtrack az Illumina-val működik, akár 100 bp-ig, a BWA-SW és a BWA-MEM pedig 70 és 1 millió bp közötti hosszabb szekvenciákkal is működhet. A BWA-MEM a legújabb verzió, jobb minőségű és pontosabb.
A BWA-SW és a BWA-MEM képes kiméra értékeket találni. [négy]
A BWA-SW a Burrows-Wheeler transzformációt használja a Smith-Waterman kiegyenlítéssel együtt. Képes hosszú sorozatokkal dolgozni, ugyanakkor pontosabb és gyorsabb, mint a BLAT. [5]
A nukleotidadatok hatékony helyi összehangolását jelenti. A Solexa fejlesztette, majd az Illumina felvásárolta.
Páros végű leolvasást használ, képes azonosítani a szerkezeti lehetőségeket. [6] Csak legfeljebb 32 bázispár hosszúságú szekvenciákkal működik, legfeljebb két eltérést engedélyez, de indelekkel nem. [7]
Hézagmentes igazítást biztosít. Egyvégű olvasás esetén az indítási lehetőségektől függően akár 2 vagy 3 eltérést is találhat. Legfeljebb 1 eltérést tesz lehetővé a páros végű olvasásoknál. [nyolc]
Statisztikai modell alapján konszenzust épít ki. [9]
Igazítja az Illumina egyvégű és páros végű olvasatait, a 454-től a párosított végű olvasatokat. Képes felismerni a hézagokat vagy eltéréseket tartalmazó igazításokat. Jelenthet többszörös igazítást. [tíz]
Az SHRiMP2 a pontosságra helyezi a hangsúlyt, lehetővé téve az olvasások polimorfizmusokhoz vagy szekvenálási hibákhoz való igazítását.
Smith-Waterman algoritmust használ. Az 1-es verzió az olvasást, a 2-es verzió a genomot indexelte, aminek köszönhetően nagyobb sebességet ért el.
Támogatja az Illumina/Solexa, Roche/454 és AB/SOLiD olvasást, támogatja a párhuzamos számítást. [tizenegy]
Egybeolvasható és párvégű töredékeket képes igazítani. Képes intronokkal dolgozni.
Az algoritmus a 2way-BWT (2BWT) indexet használja [12] . A SOAP3 verzió GPU-ra optimalizált, és speciális GPU-2BWT indexet használ [13] .
RNA-seq olvasási igazító program Bowtie alapján.
Úgy hozták létre, hogy az Illumina Genome Analyzer által előállított leolvasásokkal működjön, de sikeresen alkalmazták más technológiák által generált leolvasásokkal is. 75 bázispár vagy annál hosszabb leolvasásra optimalizálva. Nem teszi lehetővé a páros és egyvégű olvasmányok összekeverését.
| Program | Algoritmus | páros végű/egyvégű | Rések (intronok) | indels | Helyettesítések | Olvasási hossz (bp) |
|---|---|---|---|---|---|---|
| BFAST | Smith-Waterman. Létezik BWT-s verzió is | +/+ | + | + | ||
| BLAT | K-mértékek (mint BLAST) | + | 1-2 | 1-2 | ||
| Csokornyakkendő | Burroughs-Wheeler | -/+ | + | <=100 [14] , 70-1M [15] | ||
| BWA | Burrows-Wheeler + Smith-Waterman | +/+ | + | |||
| TEHÉNANTILOP | Seed hash? | +/? | - | <=2 | 32-ig | |
| MAQ | Seed hash | +/+ | - | + [16] | 2-3 [17] egyvégű, 1 páros vég esetén | <=63 [18] |
| Novoalign | +/+ | + | + | |||
| Garnélarák | K-mérések + Smith–Waterman | +/+ | + | + | + | |
| SZAPPAN | Burroughs-Wheeler | +/+ | + | <=2 | <=60 | |
| cilinder | Burroughs-Wheeler | +/+ [19] | + | + | <=2 [20] | >=75 [21] |