Lyhytlukukartoitus ( englanniksi Short-Read Sequence Alignment, Short-Read Sequence Mapping ) on bioinformaattinen menetelmä toisen sukupolven sekvensoinnin tulosten analysointiin , jossa määritetään referenssigenomissa tai -transkriptomissa sijainteja, joista jokainen lyhyt lukema voisi saadaan suurimmalla todennäköisyydellä. Se on yleensä ensimmäinen vaihe tietojenkäsittelyssä, jos tutkittavan organismin genomi tiedetään.
Seuraavan sukupolven sekvensointialustat mahdollistavat miljoonien lyhyiden 50-500 bp:n sekvenssien tehokkaan sekvensoinnin. Tätä varten DNA- tai cDNA - molekyyli jaetaan useisiin lyhyisiin segmentteihin, jotka sitten sekvensoidaan rinnakkain. Kun näiden lyhyiden segmenttien (lukemien) sekvensoidut sekvenssit on saatu, täydellinen genomi tai cDNA-sekvenssien sarja on rekonstruoitava niistä. Tätä varten on tarpeen määrittää jokaiselle lukemalle todennäköisin sijainti referenssigenomissa.
Toisin kuin de novo -reassembly , joka kokoaa lukemat yhteen tämän tuntemattoman genomin rekonstruoimiseksi, monissa nykyisissä projekteissa on "referenssigenomi" - jo tunnettu läheinen genomi toisesta organismista. Tai se voi olla joukko viitesarjoja. Tässä tapauksessa, jotta lukema saisi jonkinlaisen merkityksen, sen sijainti vertailutiedoissa on määritettävä. Tätä prosessia kutsutaan kartoitukseksi tai kohdistukseksi . Kartoitus voi näyttää hieman erilaiselta eri tehtävissä, esimerkiksi: genomikartoituksessa suuria aukkoja ei pitäisi olla, kun taas RNA-seq:n kohdalla ne ovat sallittuja silmukoinnin vuoksi. Yleisesti ottaen kartoitustehtävät eivät ole muuttuneet viimeisen sukupolven sekvenssereiden jälkeen, mutta edellistä sukupolvea varten kehitettyjä ohjelmia ei ole suunniteltu toimimaan lisääntyneillä tietomäärillä, eivätkä ne myöskään toimi hyvin lyhyiden lukujen kanssa.
Suurin ongelma on se, että tutkittu genomi eroaa referenssigenomista genomin vaihtelun (esimerkiksi SNP: n tai indelien) sekä sekvensointivirheiden vuoksi. Tästä johtuen lukukohdan ja sen "oikea" sijainti referenssigenomissa voi olla erilainen kuin tämän alueen kohdistaminen mihin tahansa muuhun vertailugenomin paikkaan, joten kartoitusohjelmien on pystyttävä löytämään epätarkkoja osumia. Tätä varten käytetään erilaisia heuristioita. Kun tämän päälle asetetaan silmukoinnin mahdollisuus RNA-seq:n tapauksessa, ongelmasta tulee vielä monimutkaisempi.
Myös toistuviin elementteihin kuuluvat lukemat ovat ongelma. Tässä tapauksessa ei aina ole mahdollista yksiselitteisesti päättää, mihin tämä lukema kartoitetaan. Tällainen sekvenssi voidaan kartoittaa satunnaisesti mihin tahansa sopivaan kohtaan tai leimata kartoitetuksi useisiin paikkoihin.
Jos referenssigenomi on suuri ja lukuja on tehty miljardeja, kartoitusaika on suuri ongelma. Kohdistus on aina ollut äärimmäisen resurssiintensiivinen tehtävä, mutta tässä tapauksessa ongelma nousee laadullisesti uudelle tasolle, joka vaatii poikkeuksellista rationaalisuutta ja tehokasta prosessoriajan ja muistin käyttöä algoritmeilta.
Näiden ongelmien ratkaisemiseen on kaksi päätapaa: hash-taulukoiden ja päätepuiden tai taulukoiden käyttäminen.
Hajautusprosessi on monta kertaa nopeampi ja halvempi kuin klassinen kohdistus, jossa käytetään Smith-Waterman-algoritmin dynaamista ohjelmointia .
Tämä lähestymistapa käyttää hash -funktiota, jonka avulla voit muuntaa merkkijonon avaimeksi, jota voidaan käyttää pikahauissa. Helpoin tapa olisi jakaa genomi sanoiksi, jotka vastaavat lukemisen pituutta, mutta tämä lähestymistapa ei toimi, koska pitkät sanat ovat todennäköisemmin ainutlaatuisia ja niiden tallennus vie liikaa muistitilaa. Sen sijaan käytetään lyhyempien osien tiivistämistä, jotka ovat paljon yleisempiä. Kun hash-funktio on saanut sopivat paikat, voidaan yrittää kartoittaa loput lukemasta genomiin. Myös lähestymistapa, jossa lukema jaetaan useisiin osiin, mahdollistaa korvausten mahdollisuuden sisällyttämiseen algoritmiin. Joten Maq-ohjelmassa lukema on jaettu 4 osaan, joita kutsutaan siemeniksi (lyhyet osat tarkalla vastaavuudella). Jos lukema sopii täydellisesti referenssiin, kaikki 4 siementä sopivat täydellisesti. Jos lukemassa on yksi epäsuhta, joka johtuu todennäköisesti SNP :iden läsnäolosta tai sekvensointivirheistä, se putoaa yhteen siemenistä, kun taas muut 3 kartoittavat edelleen täydellisesti. Samoin kahdella vaihdolla vähintään kaksi siementä sopii täydellisesti. Näin ollen kartoittamalla kaikki mahdolliset lukuparit indeksoinnilla (niitä tulee olemaan 6, koska siementen on mentävä tietyssä järjestyksessä), saamme genomiin rajoitetun joukon paikkoja, joihin koko luku voidaan kartoittaa, kun jossa on mahdollista käyttää tavallista kohdistusta sen määrittämiseksi, mikä asennoista sopii parhaiten (katso kuva 1a). SOAP, RMAP ja SeqMap toimivat samalla tavalla.
Tämän lähestymistavan muunneltuna voi olla ajatus ottaa huomioon kaikki lukemisen k-mitat tietynpituisten ei-päällekkäisten osien sijaan. Joten ACGT:n lukemista varten niitä on kolme: AC, CG, GT. SHRiMP2 ja RazerS toimivat samalla tavalla. Tämä lisää herkkyyttä, mutta lisää myös ajan kustannuksia.
Kaikki nämä tiedot vievät paljon muistitilaa. Muistin kulutuksen vähentämiseksi useimmat ohjelmat käyttävät kaksibittistä nukleotidien koodausta (A 00, C 01, G 10, T 11), mutta tämä ei salli moniselitteisen nukleotidin N käyttöä, joka voi olla läsnä sekä luku- että referenssigenomissa. Ohjelmat käyttävät erilaisia lähestymistapoja tämän kiertämiseksi. Joten BWA korvaa N:n satunnaisella nukleotidilla ja SOAP2 korvaa kaiken N:n G:llä.
Erilaisia parannuksia voidaan käyttää algoritmien nopeuttamiseen ja virheiden kiertämiseen. Käytä esimerkiksi välinpitämättömiä paikkoja (merkitkäämme ne X:llä). Joten ACGxACG siemen kohdistetaan sekä ACGAACG:n että ACGCACG:n suhteen, mikä lisää kartoituksen herkkyyttä (vaikka se lisää käsittelyaikaa, koska jokaisella lukemalla on enemmän löytöjä). Tätä käytetään ohjelmissa, kuten Zoom, BFAST, GASSST, SHRiMP2, PerM.
Suurimman osan ajasta algoritmit eivät käytä siementen etsimiseen, vaan ympäristönsä tarkistamiseen. Useimmat ohjelmat käyttävät Needleman-Wunsch-algoritmia tai sen muunnelmia. Toiset, kuten GASSST, lisäävät välivaiheen, jossa mitataan Euler-etäisyys, joka yksinkertaisesti ottaa huomioon identtisten kirjainten määrän. Jos esimerkiksi yritämme kartoittaa lukua, joka sisältää 5 G:tä, alueelle, joka sisältää vain 1 G:n, meillä on vähintään 4 korvausta. Tämän lähestymistavan avulla voit karsia nopeasti pois sopimattomat alueet ja soveltaa tarkempia (mutta myös kalliita) lähestymistapoja vain lupaaville alueille.
On mahdollista tiivistää ei genomia ja etsiä siitä lukuja, vaan tiivistää lukemia ja etsiä niistä samanpituisia genomin osia. Varhaiset Maq-, Rmap- ja SeqMap-versiot käyttivät tätä lähestymistapaa, mutta sen jälkeen yhden kokeen lukumäärä on kasvanut huomattavasti ja tämä lähestymistapa on lakannut olemasta järkevä.
Hajautusalgoritmit eivät kestä hyvin toistoja, sillä tarkistettavien siementen määrä kasvaa huomattavasti. Tämän ratkaisemiseen käytetään suffiksipuihin ja suffiksitaulukoihin perustuvia algoritmeja . Tämän lähestymistavan etuna on erityisesti se, että toistot eivät pidennä algoritmin ajoaikaa, koska toistuvat osiot "kutistuvat" suffiksipuussa. Puhtaimmillaan tämä lähestymistapa toimii erittäin nopeasti, jos siinä ei ole virheitä ja vaihtoja (esimerkiksi MPscan-ohjelma käyttää sitä).
Suffiksitaulukkoa käytetään muistin säästämiseen. Yleensä haku suffiksitaulukon kautta ei pohjimmiltaan eroa suffiksipuun kanssa työskentelystä, mutta vaatii hieman monimutkaisempaa lähestymistapaa. Burroughs-Wheeler-muunnoksia käytetään usein . Kaikkien muunnosten jälkeen tällaisen suffiksitaulukon koko on verrattavissa alkuperäisen genomin kokoon. Joten koko ihmisgenomille rusettiohjelman luoma päätetaulukko vie 2 gigatavua. Vertailun vuoksi hash-pohjaisten indeksien tietokanta (kuten Maq-ohjelmassa käytetty) vie noin 50 gigatavua muistia.
Ferragin-Manizi-algoritmia käytetään sanojen etsimiseen .
Yksinkertaistetussa muodossa prosessi on seuraava. Lukemat kohdistavat yhden nukleotidin Burrows-Wheeler-transformoituun genomiin. Jokainen kohdistettu nukleotidi antaa ohjelman kaventaa paikkojen määrää, joihin koko luku voi mennä. Jos ohjelma ei löydä kohtaa, johon lukema sopii täydellisesti, se palaa edelliseen vaiheeseen, tekee korvaavan ja jatkaa hakua. Näin toimii esimerkiksi SHRiMP. Toisaalta, jos sallittujen virheiden määrä on suuri, tämä alkaa hidastaa algoritmia. Hieman mielenkiintoisempaa modifikaatiota on käytetty BWA-ohjelmassa - se kohdistaa ensin luetun vasemman ja oikean osan olettaen, että ainakin toisessa näistä kahdesta alueesta on vähemmän virheitä (mikä perustuu siihen, että 5'-pää on yleensä paremmin järjestyksessä).
Tällä hetkellä on olemassa ohjelmia, jotka käyttävät sekä yhtä että toista lähestymistapaa. Huolimatta siitä, että Burroughs-Wheeler-muunnoksiin perustuvat ohjelmat ovat nyt suositumpia, ei voida sanoa, että tämä lähestymistapa olisi parempi. Nämä ohjelmat käsittelevät toistoja nopeammin ja paremmin kuin hash-pohjaiset ohjelmat, mutta ne eivät todennäköisesti käsittele virheitä. Toisen tyyppisillä ohjelmilla on havaittavissa päinvastainen tilanne: hajautus mahdollistaa virheiden huomioimisen, mutta se alkaa kuluttaa paljon aikaa, kun kohtaa toistoja.
Tässä tapauksessa silmukoinnin mahdollisuus tulisi ottaa huomioon. Pohjimmiltaan hyödynnetään tietoa jo tunnetuista eksoneista ja introneista, mikä mahdollistaa eksoni-eksoni-assosiaatioista koostuvan tietokannan luomisen ja jo siihen tavanomaisten algoritmien, kuten bowtie tai maq, toteuttamisen. Ilmeisesti tämä lähestymistapa ei ota huomioon aiemmin tuntemattomia introneita, joten se voidaan yhdistää koneoppimiseen tuntemattomien silmukoiden ennustamiseksi.
Toinen lähestymistapa ei ehkä käytä huomautusta ollenkaan. Toimintatavassa ilman huomautuksia TopHat määrittää ensin mahdolliset eksonit, rakentaa tietokannan mahdollisista silmukointikohteista näiden tietojen perusteella ja sitten kartoittaa lukemat sen avulla. Mahdolliset eksonit määräytyvät vierekkäisten RNA-seq-lukemien sijaintien perusteella, kun ne on kohdistettu genomiin. Koska monet eksonit ovat lyhyempiä kuin nykyisten lukusekvenssereiden tuottamat, niitä ei havaita alkuperäisen kartoitusvaiheen aikana. TopHat ratkaisee tämän ongelman pääasiassa jakamalla lukemat lyhyemmiksi paloiksi ja kartoittamalla ne itsenäisesti.
TopHat käyttää kahta päämenetelmää mahdollisten liitoskohtien tunnistamiseen. Ensimmäinen ja tärkein tekijä mahdollisen silmukointikohdan puolesta on se, kun kaksi segmenttiä yhdestä lukemisesta (lukemissa, joiden pituus on vähintään 45 emäsparia) kartoitetaan tietylle etäisyydelle toisistaan tai kun lukualueen sisäinen segmentti ei onnistu olla kartoitettu. Toinen tekijä on "peittosaarten" parien syntyminen, jotka ovat paikkoja, joissa monet RNA-seq-lukemat kartoitetaan vierekkäin. Naapurisaaret leikataan usein yhteen ja ovat transkriptiossa vierekkäin, joten TopHat etsii tapoja yhdistää ne intronilla.
Annotaatiopohjaisten algoritmien suurin ongelma on, että ne ovat erittäin riippuvaisia itse merkintöjen laadusta, kun taas koneoppimista käyttävät algoritmit ovat erittäin riippuvaisia harjoitusjoukon laadusta. Lisäksi, koska uudet merkinnät perustuvat vanhoihin, merkintöjen virheet voivat "leviää", tulla yhä "merkittävimmiksi" ja paljon vaikeammin havaittavissa.
Lyhenne englannista. Blat-tyyppinen nopea ja tarkka hakutyökalu . Ohjelman kehittäjät ovat keskittyneet ohjelman herkkyyteen virheille, SNP : ille ja indeleille, jolloin voit valita tasapainon nopeuden ja tarkkuuden välillä.
Tukee paritetun pään sekvensointia . Käyttää Smith-Waterman- algoritmia lopulliseen kohdistukseen tukemalla aukkoja ja pienten indelien määrittelyä [1] . Pystyy työskentelemään rinnakkaistilassa klusterissa. Ohjelmasta on olemassa versio bfast+bwa. Tukee Illumina-, ABI SOLiD-, 454- ja Helicos-tietomuotoja.
BLAST-tyyppinen kohdistustyökalu. Optimoitu nopeuteen käyttämällä ei-päällekkäisten K-fragmenttien indeksiä, joka sopii tietokoneen RAM-muistiin [2] .
Sallii yhden vaihdon ottelua kohden.
Käyttää Burrows-Wheeler-algoritmia indeksointiin. Ohjelma on optimoitu nopeudelle ja muistin kulutukselle, se voi käyttää useita prosessoriytimiä. Ilmoitettu nopeus ylittää 35 kertaa MAQ:n nopeuden ja 300 kertaa SOAPin nopeuden samoissa olosuhteissa. [3]
Sallii yhteensopimattomuudet.
Bowtien pohjalta rakennettiin TopHat-ohjelma RNA-seq-lukemien kohdistusta varten.
BWA (Biological Sequence Alignment) on kolmen ohjelman sarja: BWA-backtrack, BWA-SW ja BWA-MEM. BWA-backtrack toimii Illuminan kanssa, lukee jopa 100 bp, BWA-SW ja BWA-MEM voivat toimia pidempien sekvenssien kanssa 70 - 1 miljoonaa bp. BWA-MEM on uusin versio, laadukkaampi ja tarkempi.
BWA-SW ja BWA-MEM pystyvät löytämään kimeeriset lukemat. [neljä]
BWA-SW käyttää Burrows-Wheeler-muunnosta yhdessä Smith-Waterman-taajuuskorjauksen kanssa. Pystyy työskentelemään pitkien sarjojen kanssa, mutta tarkempi ja nopeampi kuin BLAT. [5]
Se tarkoittaa nukleotiditietojen tehokasta paikallista kohdistusta. Solexan kehittämä, jonka Illumina osti sitten.
Käyttää pari-pään lukemia, osaa tunnistaa rakenteellisia vaihtoehtoja. [6] Voi toimia vain 32 emäsparin pituisten sekvenssien kanssa, sallii enintään kaksi eroa, mutta ei voi toimia indelien kanssa. [7]
Tuottaa kohdistuksen ilman rakoja. Yhden pään lukemissa se voi löytää jopa 2 tai 3 ristiriitaa käynnistysvaihtoehdoista riippuen. Mahdollistaa jopa yhden yhteensopimattomuuden parillisen pään lukemissa. [kahdeksan]
Rakentaa konsensusta tilastollisen mallin perusteella. [9]
Tasaa yksipään ja parillisen pään lukemat Illuminasta, paritetut 454:stä. Pystyy havaitsemaan kohdistukset, joissa on aukkoja tai epäsopivuuksia. Saattaa raportoida usean kohdistuksen. [kymmenen]
SHRiMP2 korostaa tarkkuutta, mikä mahdollistaa lukujen kohdistamisen polymorfismiin tai sekvensointivirheisiin.
Käyttää Smith-Waterman-algoritmia. Versio 1 indeksoi lukuja, versio 2 indeksoi genomin, minkä ansiosta se saavutti suuremman nopeuden.
Tukee Illumina/Solexa-, Roche/454- ja AB/SOLiD-lukuja, tukee rinnakkaislaskentaa. [yksitoista]
Voi kohdistaa yhden luku- ja paripään fragmentit. Pystyy työskentelemään intronien kanssa.
Algoritmi käyttää 2way-BWT (2BWT) -indeksiä [12] . SOAP3-versio on GPU-optimoitu ja käyttää erityistä GPU-2BWT-indeksiä [13] .
Bowtie-pohjainen RNA-seq-lukukohdistusohjelma.
Se luotiin toimimaan Illumina Genome Analyzerin tuottamien lukujen kanssa, mutta sitä on käytetty menestyksekkäästi muiden tekniikoiden luomien lukujen kanssa. Optimoitu lukemaan, jonka pituus on 75 emäsparia tai enemmän. Ei salli parillisten ja yhden pään lukujen sekoittamista yhteen.
| Ohjelmoida | Algoritmi | paripää/yksipää | Aukot (intronit) | indels | Korvaukset | Lukupituus (bp) |
|---|---|---|---|---|---|---|
| BFAST | Smith-Waterman. On olemassa versio, jossa on BWT | +/+ | + | + | ||
| BLAT | K-mitat (kuten BLAST) | + | 1-2 | 1-2 | ||
| Rusetti | Burroughs-Wheeler | -/+ | + | <=100 [14] , 70-1M [15] | ||
| BWA | Burrows-Wheeler + Smith-Waterman | +/+ | + | |||
| ELAND | Siementen hajautus? | +/? | - | <=2 | 32 asti | |
| MAQ | Siementen hajautus | +/+ | - | + [16] | 2-3 [17] yksipäälle, 1 paripäiselle | <=63 [18] |
| Novoalign | +/+ | + | + | |||
| Katkarapu | K-mitat + Smith–Waterman | +/+ | + | + | + | |
| SAIPPUA | Burroughs-Wheeler | +/+ | + | <=2 | <=60 | |
| silinteri | Burroughs-Wheeler | +/+ [19] | + | + | <=2 [20] | >=75 [21] |