Soru:
Neden bazı montajcılar de Bruijn grafiklerinin oluşturulması için tek uzunluklu bir kmer'e ihtiyaç duyuyor?
Kamil S Jaron
2017-05-19 23:34:21 UTC
view on stackexchange narkive permalink

Neden SOAPdenovo2 veya Velvet gibi bazı birleştiriciler de Bruijn grafiğinin oluşturulması için tek uzunlukta k -mer boyuta ihtiyaç duyarken ABySS gibi diğer bazı derleyiciler eşit uzunlukta k -mers?

Iki yanıtlar:
#1
+28
Kamil S Jaron
2017-05-19 23:52:35 UTC
view on stackexchange narkive permalink

Velvet kılavuzundan:

palindromlardan kaçınmak için tek bir sayı olmalıdır. Çift sayı koyarsanız, Velvet sadece onu azaltır ve ilerler.

Biyolojideki palindromlar, ters tamamlayıcı diziler olarak tanımlanır. Palindrom sorunu bu incelemede açıklanmıştır:

Palindromlar, kendi kendilerine geriye katlanan yolları indükler. En az bir montajcı bunları zarif bir şekilde önler; Velvet, bir K-mer'in uzunluğu olan K'nin tuhaf olmasını gerektirir. Garip boyutlu bir K-mer, ters tamamlayıcısıyla eşleşemez.

Palindromlarla grafik oluşturmak mümkündür, ancak bu durumda yorumlama daha zor olacaktır. Yalnızca tek k -mers grafiklerine izin vermek, daha karmaşık bir grafiğin yorumlanması için bir kod yazmaktan kaçınmanın zarif bir yoludur.

Gelecekte birisinin bunu yanlış yorumlamaması için, bu bağlamdaki [palindrome] 'un (https://en.wikipedia.org/wiki/Palindromic_sequence) kendisinden biraz daha özel bir anlamı olduğu unutulmamalıdır [normalde İngilizcedir] (https : //en.wiktionary.org/wiki/palindrome).
#2
+12
ukemi
2019-04-19 05:08:30 UTC
view on stackexchange narkive permalink

Yukarıdaki yanıtı genişletmek için, açık değilse şunu gösteriyoruz:

  1. Palindromik diziler neden eşit uzunlukta olmalıdır
  2. Palindromik diziler neden de Bruijn grafiğindeki öz döngüler
  3. Bir de Bruijn grafiğindeki öz döngüleri neden sorunludur

1. Palindromik sekans ⇒ sekans çift uzunluktadır

Fikir: tek uzunlukta bir k-mer'de, orta nükleotidi ters tamamlayıcısı içinde 'çevrilir', bu nedenle ikisi asla eşit olamaz.

Palindromik bir dizinin $ X $ olduğunu varsayalım. O zaman $ X $ , $ \ bar {X} $ olarak etiketleyeceğimiz ters tamamlayıcısıyla aynıdır. .

$ X $ 'ın tek uzunlukta olduğunu varsayalım. O zaman, $ AbC $ biçimindedir, burada $ len (A) = len (C) = \ frac {len (X) -1} {2} $ ve $ len (b) = 1 $ .

Sonra

$ X = \ bar {X} \, AbC = \ overline {AbC} = \ bar {C} \ bar {b} \ bar {A} $ anlamına gelir span>

Ve dolayısıyla:

$ b = \ bar {b} $

( $ len (A) = len (C) = len (\ bar {C})) $ olduğundan beri. Ancak bu bir çelişkidir, çünkü $ b $ tek bir nükleotiddir ve onun tamamlayıcısına eşit olamaz. Bu nedenle, tek uzunluktaki k-merler palindrom oluşturamaz.

Dolayısıyla, bir palindrom oluşturan bir k-merin uzunluğu çift olmalıdır.


2. Palindromik k-merler neden kendi kendine döngüler oluşturur

Geleneksel bir de Bruijn grafiğindeki her düğüm benzersiz bir dizedir, ancak çoğu biyo-bilişim uygulamasında her bir ters tamamlayıcı k-1-mer çifti bir tek düğüm, örneğin $ k = 6 $ için:

A palindromic k-mer ( $ k \ geq 2 $ 'dan) şu biçimdedir:

$ xAy $

burada $ len (A) = k-2 $ span>, $ x = \ bar {y} $ ve $ A = \ bar {A} $ (muhtemelen boş dize).

Bu nedenle de Bruijn grafiğinde iki düğüme katkıda bulunacaktır:

  1. sol k-1-mer $ xA $
  2. sağ k-1-mer $ Ay $

Ve 1'den 2'ye giden bir kenar.

Ancak bu k-mer palindromik olduğundan, $ xA = \ overline {Ay} $ ve dolayısıyla bu iki düğüm ters tamamlayıcıdır ve dolayısıyla 'aynı' düğümdür ve bu nedenle bu kenar bu düğümde bir öz döngüdür.


3. Kendi kendine döngüler neden sorunludur?

Kendi kendine döngüler (eğer $ in \ _degree \ geq 2 $ ve $ out \ _degree \ geq 1 $ ) bir de Bruijn grafiğindeki olası Euler yollarının sayısını artırın (veya daha spesifik olarak, bu düğümü içeren bağlı bileşende, bir contig , bunların birden çok olabilir), çünkü bu düğümü her geçtiğinizde ek olası Euler yoluna sahip olursunuz.

Bu, her olası Eulerian gibi grafiği okurken belirsizliği artırır. yol, tüm dizinin ekstra olası yeniden yapılandırmasıdır.

Örneği düşünün:

enter image description here

Yalnızca bir tane var olası Euler yolu:

  • $ ABCDBE $

Ancak, bir öz döngü eklersek Yukarıda iki kez ziyaret edilen $ B $ adresinde bu, iki olası Euler yolunu ikiye katlar:

enter image description here

  • $ ABBCDBE $
  • $ ABCDBBE $

Şuna bağlı $ B $ 'a ilk ulaştığımızda mı yoksa ikinciye mi ulaştığımızda kendi kendine döngüyü geçip geçmediğimiz.

https://homolog.us/Tutorials/book4/p2.4.html "Genom birleştirme programları da k'den bile kaçınır, çünkü k bile birçok k-mer kendi dizilerinin ters tümleyicileri haline gelir. ** Bu, içinde belirsizliklere neden olur. Grafiğin iplik özgüllüğü. ** Bu nedenle, tek k değerleri tercih edilir. "
Güzel cevap @ukemi. Birinci noktanın sonucunu anlamam biraz zaman aldı, bu yüzden oraya bana yardımcı olacak bir cümle ekledim. Değişikliği tersine çevirebilmeniz hoşunuza gitmiyor, ama orada küçük bir açıklamanın iyi olacağını söyleyebilirim.
@KamilSJaron endişelenmeyin, ne kadar net olursa o kadar iyi - evet, teknik olarak onların takip etmeleri gerektiği (sadece tuhaf olmayanın aksine), ancak varoluşu göstermek örnek yoluyla önemsizdir (örneğin AT, ATAT vb).


Bu Soru-Cevap, otomatik olarak İngilizce dilinden çevrilmiştir.Orijinal içerik, dağıtıldığı cc by-sa 3.0 lisansı için teşekkür ettiğimiz stackexchange'ta mevcuttur.
Loading...