K-mer

Termín k-mer obecně označuje všechny podřetězce délky k, které jsou obsaženy v řetězci znaků. Ve výpočetní genomice označují k-mery všechny subsekvence (délky k) ze čtení získaného sekvenováním DNA . Množství k-mer možné vzhledem k řetězci znaků délky L je, zatímco počet k-mer daných n možností (4 v případě DNA, například ACTG) je . K-mery se obecně používají při sestavování sekvencí , ale lze je také použít při zarovnání sekvence . V kontextu lidského genomu byly k vysvětlení variability rychlostí mutací použity k-mery různých délek. ${\ displaystyle L-k + 1}$ $n ^ {k}$

Sekvenční sestava

Přehled

Při sestavování sekvence se k-mery obvykle používají při konstrukci grafiky De Bruijn . Aby bylo možné vytvořit De Bruijnův graf, musí se řetězce uložené na každé hraně délky navzájem překrývat podél délky, aby se vytvořil vrchol. Sekvence generované metodou sekvenování příští generace mají obvykle během jedné relace čtení různé délky. Například sekvence čtené sekvenční technologií Illumina produkují sekvence, které lze zachytit k-merem 100. Problém se sekvenováním však spočívá v tom, že malá část k-meru 100, ze 100-mer, přítomná v genom jsou ve skutečnosti skutečně generovány. Je to způsobeno chybami čtení, ale co je důležitější, jednoduchými otvory v krytu, které se vyskytnou během řazení. Problém je v tom, že tyto malé „zkorumpované“ k-mer zlomky porušují hlavní předpoklad v Bruijnových grafech, že všechny k-mer ze čtených sekvencí se musí překrývat u k-mers v genomu délkovým překrytím (což se nemůže stát, když všechny k-mery nejsou přítomny). Řešením tohoto problému je zmenšit velikost těchto k-moří na malá k-moře, takže malá k-moře představují všechna menší k-moře přítomná v genomu. Kromě toho rozdělení k-merů na menší velikosti také pomáhá zmírnit problém různých počátečních délek čtení. Příklad řešení rozdělení přečtené sekvence na malé k-mery je znázorněn na obrázku 1. V tomto příkladu 5-nukleotidové sekvence nezohledňují všechny 7-délkové k-mery genomu a v tomto příkladu v případě, že nelze vytvořit graf de Bruijn. Ale když jsou rozděleny na k-mery délky 4, výsledné subsekvence jsou četné a dostatečně rozmanité, aby rekonstruovaly genom pomocí de Bruijnova grafu. $L$ ${\ displaystyle L-1}$ $k-1$

Volba velikosti k-moří

Volba velikosti k-mer má mnoho různých účinků na sestavení sekvencí. Tyto efekty se velmi liší mezi menšími velikostmi k-moří a většími velikostmi k-moří. Aby bylo možné zvolit vhodnou velikost, která vyvažuje účinky, musí být známo znalost různých velikostí k-merů. Účinky velikostí jsou popsány níže.

Malá velikost k-merů

Snížení velikosti k-mer sníží rozmanitost sekvencí uložených v grafu v důsledku snížení možností kombinací a jako takové pomůže snížit množství prostoru potřebného pro uložení sekvence DNA.
Mít menší velikost zvýší šance, že se všechny k-mery budou překrývat, a tedy i posloupnosti, aby se vytvořil de Bruijnův graf.
Avšak tím, že máme menší velikost k-meru, existuje riziko, že bude mít v grafu mnoho překrytí pro jeden k-mer. Rekonstrukce genomu bude proto obtížnější, protože bude existovat vyšší počet nejednoznačných cest kvůli většímu množství k-mer, které bude nutné projet.
Informace se ztratí, když se k-moře zmenší.
- Např. Možnosti kombinací pro AGTCGTAGATGCTG jsou menší než možnosti pro ACGT, a proto první obsahuje více informací (další informace viz entropie (teorie informací)).
Menší k-mery představují problém, že nejsou schopny vyřešit určité body v DNA, například v mikrosatelitech, kde se může vyskytnout více opakování. Důvodem je skutečnost, že malá k-moře budou mít tendenci se v těchto opakovaných oblastech vracet úplně sama na sebe, a proto je obtížné určit, kolik opakování se skutečně odehrálo.
- Např. Pro subsekvenci ATGTGTGTGTGTGTACG bude počet opakování TG ztracen, pokud je zvolen k-mer velikosti menší než 16. Je to proto, že většina k-mer se vrátí do oblasti opakování a počet opakování stejného k-mer bude ztracen, místo aby zmínil počet opakování.

Velká velikost k-merů

Větší velikost k-merů zvýší množství okrajů v grafu, což zase zvýší množství paměti potřebné k uložení sekvence DNA.
Zvětšením velikosti k-meru se také sníží počet vrcholů. To pomůže při konstrukci genomu, protože v grafu bude méně cest.
Větší velikost k-mer také představuje vyšší riziko, že nevyjde ven z vrcholů každého k-mer. Z tohoto důvodu větší velikost k-mer zvyšuje riziko, že se nebudou překrývat s jiným k-merem po dobu . To proto může vést k nesouvislosti ve sledu čtení a jako takové může vést k většímu množství malých kontigů . $k-1$
Větší velikost k-mer pomáhá zmírnit problém malých opakujících se oblastí. To je způsobeno skutečností, že k-mer bude obsahovat rovnováhu mezi oblastí opakování a sekvencemi DNA (vzhledem k tomu, že jsou poměrně velké), což může pomoci vyřešit počet opakování v této oblasti.

Aplikace k-moří v bioinformatické analýze

Četnost souboru k-merů, v genomu druhu, v genomové oblasti nebo ve třídě sekvencí, lze použít jako podsekvenci "podpisu". Porovnání těchto frekvencí je matematicky jednodušší než zarovnání sekvence a je důležitou metodou při zarovnání bez sekvenční analýzy. Může být také použit jako první krok analýzy před zarovnáním.

separace různých druhů ve směsi genetického materiálu ( metagenomika , mikrobiom ); lze přidat fáze / informační rámce
Molekulární čárové kódy (čárové kódy DNA) druhů
sestava de novo
klasifikace lidské mitochondriální haploskupiny
detekovat nesprávné shromáždění genomu
de novo detekce opakované sekvence jako transponovatelného prvku
charakterizovat protein vázající sekvenční motiv. Kromě k-mer mohou být také použity nařezané k-mery (také nazývané rozteč q-gramů nebo rozteč semen).
identifikace mutací nebo polymorfismu pomocí sekvenování dat nové generace
charakterizace ostrova CpG přilehlými oblastmi
detekovat horizontální převody
detekovat bakteriální kontaminaci v sestaveném eukaryotickém genomu
detekovat rekombinaci místa
pomocí frekvence k-mer proti hloubce k-mer k odhadu velikosti genomu
odhad podílu sekvenované RNA

Pseudo kód

Určení velikosti čtení k-merů lze provést jednoduchým procházením délky řetězce, postupným zvyšováním polohy v řetězci a převzetím každého dílčího řetězce délky k. Pseudokód, který provádí tuto operaci, je následující:

fonction K-mer(Chaine_caractere, k) /* k = longueur de chaque k-mer */ n = longueur(Chaine_caractere) /* Boucle sur la longueur de Chaine_caractere jusque la longueur Chaine_caractere - taille des k-mer */ Pour i = 1 jusque n-k+1 inclus fait : /* Sort chaque K-mer de longueur k, de la position i à la position i+k dans Chaine_caractere */ sortie Chaine_caractere[position i -> position i+k] Fin de Boucle Fin de fonction

V pythonu 3 bude možné implementovat kód následujícím způsobem:

def kmer(sequence, k) : # sequence correspond a la sequence ADN, k correspond a la longueur des k-mer n = len(sequence) kmers = [] for i in range(0,n-k) : kmers.append(sequence[i:i+k]) return kmers

Příklady

Zde je několik příkladů ukazujících možné k-mery (specifikující hodnotu k) ze sekvencí DNA:

Lecture: AGATCGAGTG 3-mers: AGA GAT ATC TCG CGA GAG AGT GTG Lecture: GTAGAGCTGT 5-mers: GTAGA TAGAG AGAGC GAGCT AGCTG GCTGT

Reference

P. Compeau , P. Pevzner a G. Teslar , „ Jak aplikovat z Bruijnových grafů na genomové seskupení “, Nature Biotechnology , sv. 29, n o 11,2011, str. 987–991 ( PMID 22068540 , PMCID 5531759 , DOI 10.1038 / nbt.2023 )
Kaitlin E Samocha , Elise B Robinson , Stephan J. Sanders a Christine Stevens , „ Rámec pro interpretaci de novo mutací u lidských chorob “, Nature Genetics , sv. 46, n o 9,2014, str. 944–950 ( ISSN 1061-4036 , PMID 25086666 , PMCID 4222185 , DOI 10.1038 / ng.3050 )
Varun Aggarwala a Benjamin F Voight , „ Rozšířený sekvenční kontextový model široce vysvětluje variabilitu úrovní polymorfismu napříč lidským genomem “, Nature Genetics , sv. 48, n O 4,2016, str. 349–355 ( ISSN 1061-4036 , PMID 26878723 , PMCID 4811712 , DOI 10.1038 / ng. 3511 )
Zerbino, Daniel R. a Birney, Ewan, „ Velvet: algoritmy pro de novo krátké čtení sestavy pomocí de Bruijnových grafů “, Genome Research , sv. 18, n o 5,2008, str. 821–829 ( PMID 18349386 , PMCID 2336801 , DOI 10.1101 / gr.074492.107 )
„Rachid Ounit, Steve Wanamaker, Timothy J Close a Stefano Lonardi“ , „ CLARK: rychlá a přesná klasifikace metagenomických a genomických sekvencí pomocí diskriminačních k-merů “, BMC Genomics , sv. 16,2015, str. 236 ( PMID 25879410 , PMCID 4428112 , DOI 10.1186 / s12864-015-1419-2 )
Dubinkina, Ischenko, Ulyantsev, Tyakht, Alexeev , „ Posouzení použitelnosti k-merového spektra pro metagenomickou analýzu nepodobnosti “, BMC Bioinformatics , sv. 17,2016, str. 38 ( PMID 26774270 , PMCID 4715287 , DOI 10.1186 / s12859-015-0875-7 )
Zhu, Zheng , „ Samoorganizující se přístup pro meta-genomy “, Computational Biology and Chemistry , sv. 53,2014, str. 118–124 ( PMID 25213854 , DOI 10.1016 / j.compbiolchem.2014.08.016 )
Chor, Horn, Goldman, Levy, Massingham , „ K-mer spektra genomické DNA: modely a modality “, Genome Biology , sv. 10, N O 10,2009, R108 ( PMID 19814784 , PMCID 2784323 , DOI 10.1186 / gb-2009-10-10-r108 )
Meher, Sahu, Rao , „ Identifikace druhů na základě čárového kódu DNA pomocí vektoru funkcí k-mer a klasifikátoru náhodných lesů “, Gene , sv. 592, n O 22016, str. 316–324 ( PMID 27393648 , DOI 10.1016 / j.gene.2016.07.010 )
Li a kol. , „ Sestavení lidských genomů de novo s masivně paralelním sekvenováním krátkého čtení “, Genome Research , sv. 20, n O 22010, str. 265–272 ( PMID 20019144 , PMCID 2813482 , DOI 10.1101 / gr.097261.109 )
Navarro-Gomez a kol. , „ Phy-Mer: nový srovnávací a na referenci nezávislý klasifikátor mitochondriální haploskupiny “, Bioinformatics , sv. 31, n o 8,2015, str. 1310–1312 ( PMID 25505086 , PMCID 4393525 , DOI 10.1093 / bioinformatika / btu825 )
Phillippy, Schatz, Pop , „ Forenzní genomové shromáždění: hledání nepolapitelného nesprávného shromáždění “, Bioinformatics , sv. 9, n o 3,2008, R55 ( PMID 18341692 , PMCID 2397507 , DOI 10.1186 / gb-2008-9-3-r55 )
Price, Jones, Pevzner , „ De novo identifikace opakovaných rodin ve velkých genomech “, Bioinformatics , sv. 21 (supp 1),2005, i351–8 ( PMID 15961478 , DOI 10.1093 / bioinformatika / bti1018 )
Newburger, Bulyk , „ UniPROBE: online databáze dat mikropolí vázajících proteiny na interakcích protein - DNA “, Nucleic Acids Research , sv. 37 (supp 1), n o Database issue,2009, D77–82 ( PMID 18842628 , PMCID 2686578 , DOI 10.1093 / nar / gkn660 )
Lepší filtrování s mezerami q-gramů , obj. 56, sb. "Lecture Notes in Computer Science" ( n O 1-2)2002, 51–70 s. ( ISBN 978-3-540-43862-5 , DOI 10.1007 / 3-540-45452-7_19 , číst online )
Keich a kol. , „ O rozmístěných semenech pro hledání podobnosti “, Discrete Applied Mathematics , sv. 138, n o 3,2004, str. 253–263 ( DOI 10.1016 / S0166-218X (03) 00382-2 )
Ghandi a kol. , „ Vylepšená predikce regulační sekvence využívající mezerové funkce k-mer “, PLoS Computational Biology , sv. 10, n o 7,2014, e1003711 ( PMID 25033408 , PMCID 4102394 , DOI 10.1371 / journal.pcbi.1003711 , Bibcode 2014PLSCB..10E3711G )
Nordstrom a kol. , „ Identifikace mutace přímým porovnáním dat sekvenování celého genomu od jedinců mutantního a divokého typu pomocí k-merů “, Nature Biotechnology , sv. 31, n O 4,2013, str. 325–330 ( PMID 23475072 , DOI 10.1038 / nbt.2515 )
Chae a kol. , „ Srovnávací analýza pomocí vzorců K-mer a K-flank poskytuje důkazy o vývoji sekvence ostrovů CpG v genomech savců “, Nucleic Acids Research , sv. 41, n o 9,2013, str. 4783–4791 ( PMID 23519616 , PMCID 3643570 , DOI 10.1093 / nar / gkt144 )
Mohamed Hashim, Abdullah , „ Vzácná k-mer DNA: Identifikace sekvenčních motivů a predikce ostrova CpG a promotoru “, Journal of Theoretical Biology , sv. 387,2015, str. 88–100 ( PMID 26427337 , DOI 10.1016 / j.jtbi.2015.09.014 )
Jaron, Moravec, Martinkova , „ SigHunt: vyhledávač horizontálního přenosu genů optimalizovaný pro eukaryotické genomy “, Bioinformatics , sv. 30, n o 8,2014, str. 1081-1086 ( PMID 24371153 , DOI 10,1093 / bioinformatiky / btt727 )
Delmont, Eren , „ Identifikace kontaminace pomocí pokročilých postupů vizualizace a analýzy: metagenomické přístupy pro sestavy eukaryotického genomu “, PeerJ , sv. 4,2016, e1839 ( DOI 10.7717 / Fpeerj.1839 )
Bemm a kol. , „ Tardigrádní genom: Horizontální přenos genů nebo bakteriální kontaminace? ”, Proceedings of the National Academy of Sciences , vol. 113, n o 22,2016, E3054 - E3056 ( PMID 27173902 , PMCID 4896698 , DOI 10.1073 / pnas.1525116113 )
Wang, Xu, Liu , „ Identifikace rekombinačních skvrn na základě k-merů s mezerami “, Scientific Reports , roč. 6,2016, str. 23934 ( PMID 27030570 , PMCID 4814916 , DOI 10.1038 / srep23934 , Bibcode 2016NatSR ... 623934W )
Hozza, Vinar, Brejova (2015). "Jak velký je ten genom?" odhad genomesize a pokrytí z k-mer spektra abundance “v SPIRE 2015 ( DOI : 10.1007 / 978-3-319-23826-5_20 ).
Lamichhaney a kol. , „ Strukturální genomové změny jsou základem alternativních reprodukčních strategií v ruffu (Philomachus pugnax) “, Nature Genetics , sv. 48, n o 1,2016, str. 84-88 ( PMID 26569123 , DOI 10,1038 / ng.3430 )
Patro, Mount, Kingsford , „ Sailfish umožňuje kvantifikaci izoformy bez zarovnání ze čtení RNA-seq pomocí lehkých algoritmů “, Nature Biotechnology , sv. 32, n o 5,2014, str. 462–464 ( PMID 24752080 , PMCID 4077321 , DOI 10.1038 / nbt.2862 , arXiv 1308.3700 )

externí odkazy