K-meer

K-meer (ingl k-mer) on k nukelotiidi pikkune oligomeer, mida kasutatakse enamasti bioinformaatika probleemide lahendamiseks. Näiteks 20-meer tähistab 20 nukleotiidi pikkust oligomeeri.
Paljudel bioinformaatilistel analüüsidel, kus eelkõige on vaja võrrelda teatavate järjestuste suhtelisi või absoluutseid esinemissagedusi, on k-meeride sageduste lugemisel põhinev analüüs tehniliselt lihtsam ja kiirem, kui lugemite paigutamisel põhinevad analüüsid. Keskendudes DNA järjestusele võib oligomeere vaadelda järjestusena, mis on koostatud nukleotiide sisaldava tähestiku Σ = {A, C, G, T} põhjal. DNA järjestuses pikkusega L esineb kokku (L ‒ k + 1) k-meeri.
Erinevaid võimalikke k-meere on 4ᵏ. K-meeride kasutamisel geneetilistes testides pakuvad pikemad k-meerid suuremat spetsiifilisust, kuid madalamat sensitiivsust. Lühikesed k-meerid on väiksema spetsiifilisusega, kuid kõrgema sensitiivsusega.

K-meeride loendamise programmid

Seni on levinumad k-meeride loendamiseks mõeldud programmid KMC2, DSK2, Jellyfish, GenomeTester4 ja KCMBT. Lisaks huvitav programm Gerbil, mis kasutab graafikakaarti protsessorit (GPU) arvutusteks. Programmide puhul hinnatakse kiirust, mälu ning kettaruumi efektiivset kasutust.

KMC2

KMC (ingl K-mer Counter) 2 on Sileesia Tehnikaülikoolis välja töötatud k-meeride loendusprogramm, mille plussideks on kiirus ning vähene mälukasutus. KMC-s kasutusel olev algoritm kasutab eeskätt kõvakettaruumi, mitte muutmälu, ning see võimaldab KMC-d ka tänapäevastel personaalarvutitel kasutada. Alates versioonist 2.3.0 on KMC-ga võimalik sooritada k-meeride tabelfailidega hulgateoreetilisi tehteid (leida ühendit, ühisosa ja vahet) ning k-meere sorteerida ja vastavalt arvukusele filtreerida ehk eemaldada liiga haruldased ja/või sagedased k-meerid. Operatsioonisüsteemidest on toetatud Linux, OS X ja Windows. Ühe haruga F.vesca 28-meeri loetakse ära, kasutades 12 GB RAM ja 4 GB kettaruumi 298 sekundi jooksul.

DSK2

DSK2 (ingl disk streaming of k-mers) K-meeride loendamine kasutab vähe mälu, mis vajab ainult fikseeritud sisestatud arvu mälu ja kettaruumi. Selline lähenemine realiseerib mälu, aja ja ketta kompromissi. Kõigi k-meeriate komplekt kõigist lehtedest on jaotatud ja partitsioonid salvestatakse kettale. Seejärel laaditakse iga partitsioon ajutises räsilaual olevasse mällu eraldi. K-meeri loendused tagastatakse iga räsitabeli läbimisega. Madalad arvukad k-meerid on valikuliselt filtreeritud. DSK on esimene lähenemisviis, mis suudab lugeda kõiki inimese genoomi andmekogumi 27-meeri, kasutades ainult 4,0 GB mälu ja mõõdukat kettaruumi (160 GB) 17,9 tunni jooksul.

Jellyfish2

Jellyfish 2 anti välja 2011. aastal ning toona oli tegemist kiire ning efektiivse mälukasutusega k-meeride loendusprogrammiga. Programmile on sisendiks võimalik anda üks või enam FASTA või FASTQ vormingus DNA järjestusi sisaldav fail. Väljundfail on binaarses vormingus, mida on võimalik teisendada inimloetavasse tekstivormingusse ning millest on võimalik leida ka mingi kindla k-meeri sagedus või koostada histogramm k-meeride esinemissageduste kohta. Operatsioonisüsteemidest on toetatud Linux, OS X ja Windows. Ühe haruga F.vesca 28-meeri loetakse ära, kasutades 6 GB RAM 932 sekundi jooksul.

GenomeTester4

GenomeTester4 on Tartu Ülikooli bioinformaatika õppetoolis välja töötatud tarkvarapakett, mille eeliseks võrreldes analoogsete programmidega on võimalus sooritada k-meeride tabelfailidega hulgateoreetilisi operatsioone (KMC viimases versioonis on ka see võimalus lisatud). GenomeTester 4 koosneb kolmest programmist: GListMaker, GListCompare ja GListQuery. GListMaker on mõeldud FASTA või FASTQ vormingus failidest k-meeride loendamiseks. GListCompare sooritab k-meeride binaarkujul tabelfailidega hulgateoreetilisi tehteid – võimalik on arvutada ühendit, ühisosa ja vahet.

KCMBT

KCMBT (ingl k-mer Counter based on Multiple Burst Trees) sisemälutehnika kasutab vahemälu efektseid valangu digipuid (ingl brust tries) probleemi lahendamiseks. Valangu digipuu täissõlm on jagatud mitmeks sõlmeks, et teha ruumi uute elementide sisestamiseks. See algoritm ühendab hulga võimalikke ideid kiiremaks väljundiks. Need ideed hõlmavad valangu digipuude rakendamist k-meeride salvestamiseks, arvestatakse (k+x)-meere ning ühendades k-meeri selle loendi ühte ühikut. Seni üks kiiremaid k-meeride loendamise algoritme. Ühe haruga F.vesca 28-meeri loetakse ära, kasutades 14 GB RAM 160 sekundi jooksul.

Gerbil

Gerbil on disainitud k ≥ 32 k-meeride efektiivseks lugemiseks, kasutades vähem ressursse. Lisaks põhifunktsioonidele võib programm kasutada valikuliselt graafikaprotsesse, et loendusetappi kiirendada. Tegu on kaheetapilise rakendusega, kus esimeses astmes on genoomi lugem laaditud kettalt ja jagatud ümber ajutisteks failideks. Teise sammuna loendatakse iga ajutise faili k-meerid räsitabeli abil. Genoomi andmekogudega eksperimendid näitavad, et Gerbil suudab tõhusalt toetada nii väikseid kui ka suuri k-meere. Faas ühe G. gallus 28-meeri loetakse kasutades 2,14 GB põhimälu ja 23,66 GB kettaruumi 604 sekundi jooksul.

Näited

nukleotiidid: TCTAGCTCAC
3-meerid: TCT CTA TAG AGC GCT CTC TCA CAC
nukleotiidid: CATCTCGACA
5-meerid: CATCT ATCTC TCTCG CTCGA TCGAC CGACA