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.[1] 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.[2]

Erinevaid võimalikke k-meere on 4k.[3] 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.[4]

K-meeride loendamise programmid

[muuda | muuda lähteteksti]

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

KMC2

[muuda | muuda lähteteksti]

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.[8] Ühe haruga F.vesca 28-meeri loetakse ära, kasutades 12 GB RAM ja 4 GB kettaruumi 298 sekundi jooksul.[6]

DSK2

[muuda | muuda lähteteksti]

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.[9]

Jellyfish2

[muuda | muuda lähteteksti]

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.[10] Ühe haruga F.vesca 28-meeri loetakse ära, kasutades 6 GB RAM 932 sekundi jooksul.[6]

GenomeTester4

[muuda | muuda lähteteksti]

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.[11]

KCMBT

[muuda | muuda lähteteksti]

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.[6]

Gerbil

[muuda | muuda lähteteksti]

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.[7]

K-meeride rakendused bioinformaatilises analüüsis

[muuda | muuda lähteteksti]

Näited

[muuda | muuda lähteteksti]

nukleotiidid: TCTAGCTCAC

3-meerid: TCT CTA TAG AGC GCT CTC TCA CAC

nukleotiidid: CATCTCGACA

5-meerid: CATCT ATCTC TCTCG CTCGA TCGAC CGACA

Viited

[muuda | muuda lähteteksti]
  1. ↑ Wood D., Salzberg S. (2014). Kraken: ultrafast metagenomic sequence classification using exact alignments. Genome Biology 15(3): R46.
  2. ↑ Sonnenburg, S., Zien, A., Philips, P., & Rätsch, G. (2008). POIMs: positional oligomer importance matrices—understanding support vector machine-based signal detectors. Bioinformatics, 24(13), i6– i14.
  3. ↑ Compeau, P. E., Pevzner, P. A., Tseler, G. (2011). How to apply de Bruijn graphs to genome assembly, Nat Biotechnol, 29(11), 987-91.
  4. ↑ Lees, J. A., Vehkala, M., Välimäki, N., Harris, S. R., Chewapreecha, C., Croucher, N. J., … Corander, J. (2016). Sequence element enrichment analysis to determine the genetic basis of bacterial phenotypes. Nature Communications, 7, 12797.
  5. ↑ PCR-i praimerite kvaliteedimudeli integreerimine Primer3-e disainimetoodikasse. Lepamets, Maarja TÜ MAT-INF magistritöö, juhendaja Lauris Kaplinski.
  6. ↑ 6,0 6,1 6,2 6,3 "KCMBT: a k-mer Counter based on Multiple Burst Trees".
  7. ↑ 7,0 7,1 "Gerbil: a fast and memory-efficient k-mer counter with GPU-support".
  8. ↑ Deorowicz, S., Kokot, M., Grabowski, S. (2014). KMC 2: Fast and resource-frugal k-mer counting. 1:1-21.
  9. ↑ Rizk, G., Lavenier, D., Chikhi, R. (2013). DSK: K-mer counting with very low memory usage. Bioinformatics 29:652-653.
  10. ↑ Marcais G., Kingsford C. (2011). A fast, lock-free approach for efficient parallel counting of occurrences of k-mers. Bioinformatics 27(6): 764–770.
  11. ↑ Kaplinski, L., Lepamets, M., Remm, M. (2015). GenomeTester4: a toolkit for performing basic set operations - union intersection and complement on k-mer lists. Gigascience.
  12. ↑ "Rachid Ounit, Steve Wanamaker, Timothy J Close and Stefano Lonardi" (2015). "CLARK: fast and accurate classification of metagenomic and genomic sequences using discriminative k-mers". BMC Genomics. 16: 236. PMC 4428112 . PMID 25879410. doi:10.1186/s12864-015-1419-2
  13. ↑ Dubinkina, Ischenko, Ulyantsev, Tyakht, Alexeev (2016). "Assessment of k-mer spectrum applicability for metagenomic dissimilarity analysis". BMC Bioinformatics. 17: 38. doi:10.1186/s12859-015-0875-7
  14. ↑ Chor, Horn, Goldman, Levy, Massingham (2009). "Genomic DNA k-mer spectra: models and modalities". Genome Biology. 10 (10): R108. doi:10.1186/gb-2009-10-10-r108.
  15. ↑ Meher, Sahu, Rao (2016). "Identification of species based on DNA barcode using k-mer feature vector and Random forest classifier". Gene. 592 (2): 316–324. doi:10.1016/j.gene.2016.07.010
  16. ↑ Navarro-Gomez et al. (2015). "Phy-Mer: a novel alignment-free and reference-independent mitochondrial haplogroup classifier". Bioinformatics. 31 (8): 1310–1312. doi:10.1093/bioinformatics/btu825
  17. ↑ Phillippy, Schatz, Pop (2008). "Genome assembly forensics: finding the elusive mis-assembly". Bioinformatics. 9 (3): R55. doi:10.1186/gb-2008-9-3-r55.
  18. ↑ Price, Jones, Pevzner (2005). "De novo identification of repeat families in large genomes". Bioinformatics. 21(supp 1): i351–i358. doi:10.1093/bioinformatics/bti1018.
  19. ↑ Newburger, Bulyk (2009). "UniPROBE: an online database of protein binding microarray data on protein–DNA interactions". Nucleic Acids Research. 37(supp 1): D77–D82. PMC 2686578 . PMID 18842628. doi:10.1093/nar/gkn660.
  20. ↑ Nordstrom et al. (2013). "Mutation identification by direct comparison of whole-genome sequencing data from mutant and wild-type individuals using k-mers". Nature Biotechnology. 31 (4): 325–330. doi:10.1038/nbt.2515.
  21. ↑ Chae et al. (2013). "Comparative analysis using K-mer and K-flank patterns provides evidence for CpG island sequence evolution in mammalian genomes". Nucleic Acids Research. 41 (9): 4783–4791. doi:10.1093/nar/gkt144.
  22. ↑ Mohamed Hashim, Abdullah (2015). "Rare k-mer DNA: Identification of sequence motifs and prediction of CpG island and promoter". Journal ofTheoretical Biology. 387: 88–100. doi:10.1016/j.jtbi.2015.09.014
  23. ↑ Jaron, Moravec, Martinkova (2014). "SigHunt: horizontal gene transfer finder optimized for eukaryotic genomes". Bioinformatics. 30 (8): 1081–1086. PMID 24371153. doi:10.1093/bioinformatics/btt727
  24. ↑ Delmont, Eren (2016). "Identifying contamination with advanced visualization and analysis practices: metagenomic approaches for eukaryotic genome assemblies". PeerJ. 4: e1839. doi:10.7717/Fpeerj.1839.
  25. ↑ Bemm et al. (2016). "Genome of a tardigrade: Horizontal gene transfer or bacterial contamination?". Proceedings of the National Academy of Sciences. 113: E3054-E3056. doi:10.1073/pnas.1525116113
  26. ↑ Wang, Xu, Liu (2016). "Recombination spot identification Based on gapped k-mers". Scientific Reports. 6: 23934. Bibcode:2016NatSR...623934W. doi:10.1038/srep23934
  27. ↑ Hozza, Vinar, Brejova (2015). How big is that genome? estimating genomesize and coverage from k-mer abundance spectra. SPIRE 2015.
  28. ↑ Lamichhaney et al. (2016). "Structural genomic changes underlie alternative reproductive strategies in the ruff (Philomachus pugnax)". Nature Genetics. 48: 84–88. PMID 26569123. doi:10.1038/ng.3430
  29. ↑ Patro, Mount, Kingsford (2014). "Sailfish enables alignment-free isoform quantification from RNA-seq reads using lightweight algorithms". Nature Biotechnology. 32: 462–464. PMC 4077321 . PMID 24752080. doi:10.1038/nbt.2862