K-mer

Terimi k-mer genellikle bir karakter dizisi içinde bulunan uzunluk k tüm alt dizeleri ifade eder. Hesaplamalı genomikte k-merler, DNA dizilemesi ile elde edilen bir okumadan tüm alt dizileri (k uzunluğunda) ifade eder . L uzunluğunda bir karakter dizisi verildiğinde olası k-mer miktarı, n olasılık (DNA durumunda 4, örneğin ACTG) verilen k-mer sayısıdır . K-mer'ler genellikle dizi montajında kullanılır , ancak sıra hizalamasında da kullanılabilir . İnsan genomu bağlamında, mutasyon oranlarındaki değişkenliği açıklamak için farklı uzunluklardaki k-mer'ler kullanılmıştır. ${\ displaystyle L-k + 1}$ $n ^ {k}$

Sıra montajı

Genel Bakış

Sıralı montajda, k-mer'ler tipik olarak De Bruijn grafikleri oluştururken kullanılır . Bir De Bruijn Grafiği oluşturmak için, her bir kenarda depolanan dizelerin bir tepe noktası oluşturmak için bir uzunluk boyunca birbirleriyle örtüşmesi gerekir . Yeni nesil sıralama yönteminden üretilen diziler tipik olarak tek bir okuma oturumu sırasında farklı uzunluklara sahiptir. Örneğin, Illumina dizileme teknolojisi tarafından okunan diziler, 100 k-mer ile yakalanabilen diziler üretir. Bununla birlikte, dizileme ile ilgili sorun, 100-mer'in 100-mer'in küçük bir k-mer fraksiyonunun, içinde mevcut olmasıdır. aslında genom üretilir. Bunun nedeni okuma hatalarıdır, ancak daha da önemlisi sıralama sırasında oluşan basit kapak delikleridir. Sorun, bu küçük "bozuk" k-mer fraksiyonlar okuma dizilerinden tüm k-mer uzunluğu örtüşme tarafından genomun k-mer öğeleri üst üste gerektiğini, Bruijn en grafiklerde Ana varsayımı ihlal olmasıdır. (Zaman tüm olamaz hangi k-mer'ler mevcut değil). Bu sorunun çözümü, bu k-denizlerinin boyutunu küçük k-denizlerine düşürmektir, öyle ki küçük k-denizleri genomda mevcut olan tüm küçük k-denizleri temsil eder. Ek olarak, k-mer'leri daha küçük boyutlara bölmek de farklı başlangıç okuma uzunlukları sorununu hafifletmeye yardımcı olur. Okunan diziyi küçük k-merlere bölme çözümünün bir örneği Şekil 1'de gösterilmektedir. Bu örnekte, 5-nükleotid dizileri, genomun tüm 7-uzunluk k-merlerini hesaba katmaz ve bu durumda bir de Bruijn grafiği oluşturulamaz. Ancak, uzunlukları 4 olan k-merlere bölündüklerinde, ortaya çıkan alt diziler çoktur ve bir de Bruijn grafiği kullanarak genomu yeniden yapılandırmak için yeterince çeşitlidir. $L$ ${\ displaystyle L-1}$ $k-1$

K-denizlerinin boyutunun seçimi

K-merlerin boyutunun seçimi, dizilerin montajı üzerinde birçok farklı etkiye sahiptir. Bu etkiler, daha küçük boyutlu k-denizleri ve daha büyük k-denizleri arasında büyük farklılıklar gösterir. Bu nedenle, etkileri dengeleyen uygun bir boyut seçmek için farklı boyutlarda k-merlerin anlaşılması bilinmelidir. Boyutların etkileri aşağıda açıklanmıştır.

Küçük bir k-mer boyutu

K-mer boyutundaki bir azalma, kombinasyon olasılıklarındaki azalma nedeniyle grafikte depolanan dizilerin çeşitliliğini azaltacak ve bu nedenle bir DNA dizisini depolamak için gereken alan miktarını azaltmaya yardımcı olacaktır.
Daha küçük bir boyuta sahip olmak, tüm k-mer'lerin üst üste gelme olasılığını ve bu nedenle de Bruijn grafiğini oluşturmak için alt dizileri artıracaktır.
Bununla birlikte, daha küçük bir k-mer boyutuna sahip olarak, tek bir k-mer için grafikte birçok örtüşme riski vardır. Bu nedenle, genomun yeniden yapılandırılması daha zor olacaktır çünkü seyahat edilmesi gerekecek olan daha fazla miktarda k-mer nedeniyle daha fazla sayıda belirsiz yol olacaktır.
K-denizler küçüldüğünde bilgi kaybolur.
- Örneğin. AGTCGTAGATGCTG için kombinasyon olasılıkları ACGT için olanlardan daha azdır ve bu nedenle ilki daha fazla bilgi taşır (daha fazla bilgi için bkz. Entropi (bilgi teorisi) ).
Daha küçük k-merler, çoklu tekrarların meydana gelebileceği mikro uydularda olduğu gibi, DNA'daki belirli noktaları çözememe sorununu ortaya çıkarır . Bunun nedeni, küçük denizlerin bu tekrarlanan bölgelerde tamamen kendi kendilerine geri dönme eğiliminde olmaları ve bu nedenle gerçekte meydana gelen tekrarların sayısını belirlemenin zor olmasıdır.
- Örneğin. ATGTGTGTGTGTGTACG alt dizisi için, 16'dan küçük bir k-mer seçilirse TG tekrarlarının sayısı kaybolacaktır. Bunun nedeni, k-mer'in çoğunun tekrar bölgesine geri dönmesi ve tekrarların miktarından bahsetmek yerine aynı k-mer'in tekrar sayısının kaybolmasıdır.

Büyük boy k-mer'ler

Daha büyük boyutlu k-merlere sahip olmak, grafikteki kenarların miktarını artıracak ve bu da DNA dizisini depolamak için gereken bellek miktarını artıracaktır.
K-mer'in boyutunu artırarak, köşe sayısı da azalacaktır. Bu, grafikte seyahat etmek için daha az yol olacağından, genomun inşasına yardımcı olacaktır.
Daha büyük bir k-mer boyutu, her k-mer'in zirvelerinden dışarı çıkmama riskini de artırır. Bu nedenle, daha büyük bir k-mer boyutu, bir uzunluk boyunca başka bir k-mer ile çakışmama riskini arttırır . Bu nedenle, bu, okuma dizisinde sürekliliğin olmamasına yol açabilir ve bu nedenle daha büyük miktarda küçük kontiglere yol açabilir . $k-1$
Daha büyük bir k-mer boyutu, küçük tekrar bölgeleri sorununu hafifletmeye yardımcı olur. Bunun nedeni, k-mer'in tekrar bölgesi ile DNA dizileri arasında (boyut olarak oldukça büyük oldukları göz önüne alındığında) bu alandaki tekrar sayısının çözülmesine yardımcı olabilecek bir denge içereceği gerçeğidir.

Biyoinformatik analizde k-seas uygulamaları

Bir türün genomunda, bir genomik bölgede veya bir dizi sınıfında bir dizi k-mer sıklığı, bir alt dizi "imza" olarak kullanılabilir. Bu frekansları karşılaştırmak matematiksel olarak dizi hizalamadan daha kolaydır ve dizi analizi olmadan hizalamada önemli bir yöntemdir. Hizalamadan önce ilk analiz adımı olarak da kullanılabilir.

farklı türlerin genetik materyal karışımı içinde ayrılması ( metagenomik , mikrobiyom ); aşamalar / bilgi çerçeveleri eklenebilir
Türlerin moleküler barkodlaması (DNA barkodlaması)
de novo montajı
insan mitokondriyal haplogrup sınıflandırması
yanlış genom birleşimini tespit et
yeri değiştirilebilir bir eleman olarak tekrarlanan dizinin de novo tespiti
bir dizi motifi bağlayıcı proteini karakterize eder. K-mer'e ek olarak, kesilmiş k-mer'ler (aralıklı q-gramlar veya aralıklı tohumlar olarak da adlandırılır) da kullanılabilir.
Yeni nesil veri sıralaması kullanılarak mutasyonların veya polimorfizmin belirlenmesi
CpG adasının komşu bölgelere göre karakterizasyonu
yatay transferleri tespit et
birleştirilmiş bir ökaryotik genomdaki bakteriyel kontaminasyonu tespit etmek
site rekombinasyonunu tespit et
genom boyutunu tahmin etmek için k-mer frekansına karşı k-mer derinliğini kullanmak
sıralı RNA oranının tahmini

Sözde kod

K-mer'lerin okuma boyutunun belirlenmesi, basitçe tel uzunluğunun uzunluğu boyunca döngü yaparak, dizideki konumu kademeli olarak artırarak ve k uzunluğundaki her bir alt dizeyi alarak yapılabilir. Bu işlemi gerçekleştiren sözde kod aşağıdaki gibidir:

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

In piton 3, aşağıdaki gibi kod uygulamak mümkün olacaktır:

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

Örnekler

İşte DNA dizilerinden olası k-mer'leri (bir k değeri belirterek) gösteren bazı örnekler:

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

Referanslar

P. Compeau , P. Pevzner ve G. Teslar , " Bruijn grafiklerinden genom montajına nasıl uygulanır ", Nature Biotechnology , cilt. 29, n o 11,2011, s. 987–991 ( PMID 22068540 , PMCID 5531759 , DOI 10.1038 / nbt.2023 )
Kaitlin E Samocha , Elise B Robinson , Stephan J Sanders ve Christine Stevens , " İnsan hastalığında de novo mutasyonun yorumlanması için bir çerçeve ", Nature Genetics , cilt. 46, n o 9,2014, s. 944–950 ( ISSN 1061-4036 , PMID 25086666 , PMCID 4222185 , DOI 10.1038 / ng.3050 )
Varun Aggarwala ve Benjamin F Voight , " Genişletilmiş dizi bağlam modeli, insan genomu boyunca polimorfizm seviyelerindeki değişkenliği geniş bir şekilde açıklar ", Nature Genetics , cilt. 48, n, o , 4,2016, s. 349–355 ( ISSN 1061-4036 , PMID 26878723 , PMCID 4811712 , DOI 10.1038 / ng.3511 )
Zerbino, Daniel R. ve Birney, Ewan, " Velvet: de Bruijn grafikleri kullanarak de novo kısa okuma montajı için algoritmalar ", Genome Research , cilt. 18, n o 5,2008, s. 821–829 ( PMID 18349386 , PMCID 2336801 , DOI 10.1101 / gr.074492.107 )
"Rachid Ounit, Steve Wanamaker, Timothy J Close ve Stefano Lonardi" , " CLARK: ayırt edici k-merler kullanılarak metagenomik ve genomik dizilerin hızlı ve doğru sınıflandırılması ", BMC Genomics , cilt. 16,2015, s. 236 ( PMID 25879410 , PMCID 4428112 , DOI 10.1186 / s12864-015-1419-2 )
Dubinkina, Ischenko, Ulyantsev, Tyakht, Alexeev , " Metagenomik farklılık analizi için k-mer spektrum uygulanabilirliğinin değerlendirilmesi ", BMC Bioinformatics , cilt. 17,2016, s. 38 ( PMID 26774270 , PMCID 4715287 , DOI 10.1186 / s12859-015-0875-7 )
Zhu, Zheng , " Meta-genomlar için kendi kendini organize eden yaklaşım ", Hesaplamalı Biyoloji ve Kimya , cilt. 53,2014, s. 118–124 ( PMID 25213854 , DOI 10.1016 / j.compbiolchem.2014.08.016 )
Chor, Horn, Goldman, Levy, Massingham , " Genomik DNA k-mer spektrumları: modeller ve modaliteler ", Genom Biyolojisi , cilt. 10, n o 10,2009, R108 ( PMID 19814784 , PMCID 2784323 , DOI 10.1186 / gb-2009-10-10-r108 )
Meher, Sahu, Rao , " K-mer özellik vektörü ve Rastgele orman sınıflandırıcı kullanarak DNA barkoduna dayalı türlerin tanımlanması ", Gene , cilt. 592, n o 22016, s. 316–324 ( PMID 27393648 , DOI 10.1016 / j.gene.2016.07.010 )
Li ve diğerleri , "Büyük ölçüde paralel kısa okuma dizileme ile insan genomlarının De novo montajı ", Genome Research , cilt. 20, n o 22010, s. 265-272 ( PMID 20.019.144 , Bulunamayan PMCID 2.813.482 , DOI 10,1101 / gr.097261.109 )
Navarro-Gomez ve diğerleri , " Phy-Mer: yeni bir hizalamadan ve referanstan bağımsız mitokondriyal haplogrup sınıflandırıcı ", Bioinformatics , cilt. 31, n o 8,2015, s. 1310–1312 ( PMID 25505086 , PMCID 4393525 , DOI 10.1093 / biyoinformatik / btu825 )
Phillippy, Schatz, Pop , " Genom derleme adli tıp: zor yanlış birleştirmeyi bulma ", Bioinformatics , cilt. 9, n o 3,2008, R55 ( PMID 18341692 , PMCID 2397507 , DOI 10.1186 / gb-2008-9-3-r55 )
Price, Jones, Pevzner , " Büyük genomlarda tekrar ailelerin de novo tanımlanması ", Bioinformatics , cilt. 21 (ek 1),2005, i351–8 ( PMID 15961478 , DOI 10.1093 / bioinformatics / bti1018 )
Newburger, Bulyk , " UniPROBE: protein-DNA etkileşimleri üzerine protein bağlama mikroarray verilerinin çevrimiçi veritabanı ", Nucleic Acids Research , cilt. 37 (ek 1), n o Veritabanı sorunu,2009, D77–82 ( PMID 18842628 , PMCID 2686578 , DOI 10.1093 / nar / gkn660 )
Aralıklı q gramlarla daha iyi filtreleme , vol. 56, gün. "Bilgisayar Bilimlerinde Ders Notları" ( n o 1–2),2002, 51–70 s. ( ISBN 978-3-540-43862-5 , DOI 10.1007 / 3-540-45452-7_19 , çevrimiçi okuyun )
Keich ve diğerleri , " Benzerlik araması için aralıklı tohumlar üzerine ", Discrete Applied Mathematics , cilt. 138, n o 3,2004, s. 253–263 ( DOI 10.1016 / S0166-218X (03) 00382-2 )
Ghandi ve diğerleri , " Boşluklu k-mer özelliklerini kullanarak geliştirilmiş düzenleyici sıra tahmini ", PLoS Hesaplamalı Biyoloji , cilt. 10, n o 7,2014, e1003711 ( PMID 25033408 , PMCID 4102394 , DOI 10.1371 / journal.pcbi.1003711 , Bibcode 2014PLSCB..10E3711G )
Nordstrom ve diğerleri , " mutant ve vahşi tip bireylerden alınan tüm genom dizileme verilerinin k-merler kullanılarak doğrudan karşılaştırılmasıyla mutasyon tanımlama ", Nature Biotechnology , cilt. 31, n o 4,2013, s. 325–330 ( PMID 23475072 , DOI 10.1038 / nbt.2515 )
Chae ve diğerleri , " K-mer ve K-yan modellerini kullanan karşılaştırmalı analiz, memeli genomlarında CpG ada dizisi evrimi için kanıt sağlar ", Nucleic Acids Research , cilt. 41, n o 9,2013, s. 4783–4791 ( PMID 23519616 , PMCID 3643570 , DOI 10.1093 / nar / gkt144 )
Mohamed Hashim, Abdullah , " Nadir k-mer DNA: Dizi motiflerinin tanımlanması ve CpG adası ve promotörünün tahmini ", Theoretical Biology Dergisi , cilt. 387,2015, s. 88-100 ( PMID 26.427.337 , DOI 10.1016 / j.jtbi.2015.09.014 )
Jaron, Moravec, Martinkova , " SigHunt: ökaryotik genomlar için optimize edilmiş yatay gen transfer bulucu ", Bioinformatics , cilt. 30, n o 8,2014, s. 1081–1086 ( PMID 24371153 , DOI 10.1093 / bioinformatics / btt727 )
Delmont, Eren , " Gelişmiş görselleştirme ve analiz uygulamalarıyla kontaminasyonu tanımlama: ökaryotik genom toplulukları için metagenomik yaklaşımlar ", PeerJ , cilt. 4,2016, e1839 ( DOI 10.7717 / Fpeerj.1839 )
Bemm ve diğerleri , “ Bir tardigradın genomu: Yatay gen transferi mi yoksa bakteriyel kontaminasyon mu? ”, Ulusal Bilimler Akademisi Bildirileri , cilt. 113, n o 22,2016, E3054 - E3056 ( PMID 27173902 , PMCID 4896698 , DOI 10.1073 / pnas.1525116113 )
Wang, Xu, Liu , " Boşluklu k-merlere dayalı rekombinasyon nokta tanımlaması ", Scientific Reports , cilt. 6,2016, s. 23934 ( PMID 27030570 , PMCID 4814916 , DOI 10.1038 / srep23934 , Bibcode 2016NatSR ... 623934W )
Hozza, Vinar, Brejova (2015). "Bu genom ne kadar büyük? SPIRE 2015'te ( DOI : 10.1007 / 978-3-319-23826-5_20 ) k-mer bolluk spektrumlarından genom boyutu ve kapsama tahmini ” .
Lamichhaney ve diğerleri , " Yapısal genomik değişiklikler, ruff (Philomachus pugnax) içindeki alternatif üreme stratejilerinin altında yatar ", Nature Genetics , cilt. 48, n o 1,2016, s. 84-88 ( PMID 26569123 , DOI 10.1038 / ng.3430 )
Patro, Mount, Kingsford , " Sailfish, hafif algoritmalar kullanarak RNA-sekans okumalarından hizalamasız izoform ölçümü sağlar ", Nature Biotechnology , cilt. 32, n o 5,2014, s. 462–464 ( PMID 24752080 , PMCID 4077321 , DOI 10.1038 / nbt.2862 , arXiv 1308.3700 )

Dış bağlantılar