Questão:
Por que alguns montadores requerem um kmer de comprimento ímpar para a construção de gráficos de de Bruijn?
Kamil S Jaron
2017-05-19 23:34:21 UTC
view on stackexchange narkive permalink

Por que alguns montadores como SOAPdenovo2 ou Velvet exigem um tamanho k de comprimento ímpar para a construção do gráfico de Bruijn, enquanto alguns outros montadores, como ABySS, funcionam com criadores k de comprimento par?

Dois respostas:
#1
+28
Kamil S Jaron
2017-05-19 23:52:35 UTC
view on stackexchange narkive permalink

Do manual do Velvet:

deve ser um número ímpar, para evitar palíndromos. Se você colocar um número par, o Velvet irá apenas diminuí-lo e continuar.

os palíndromos em biologia são definidos como sequências complementares reversas. O problema dos palíndromos é explicado nesta revisão:

Os palíndromos induzem caminhos que se dobram sobre si mesmos. Pelo menos um montador evita isso com elegância; Velvet requer K, o comprimento de um K-mer, para ser estranho. Um K-mer de tamanho ímpar não pode corresponder ao seu complemento reverso.

É possível construir um gráfico com palíndromos, mas então a interpretação será mais difícil. Permitir apenas gráficos de k -mers ímpares é apenas uma maneira elegante de evitar a escrita de um código para interpretação de um gráfico mais complicado.

Para que no futuro alguém não interprete mal isso, deve-se observar que [palíndromo] (https://en.wikipedia.org/wiki/Palindromic_sequence) neste contexto tem um significado um pouco mais específico do que [normalmente teria em inglês] (https : //en.wiktionary.org/wiki/palindrome).
#2
+12
ukemi
2019-04-19 05:08:30 UTC
view on stackexchange narkive permalink

Para expandir a resposta acima, caso não esteja claro, mostramos:

  1. Por que as sequências palíndrômicas devem ter o mesmo comprimento
  2. auto-loops em um gráfico de Bruijn
  3. Por que os auto-loops em um gráfico de Bruijn são problemáticos

1. Seqüência palindrômica ⇒ seqüência é de comprimento par

Idéia: em um k-mer de comprimento ímpar, seu nucleotídeo do meio é 'invertido' em seu complemento reverso, então dois nunca podem ser iguais.

Suponha que você tenha uma sequência palíndrômica $ X $ . Então, $ X $ é idêntico ao seu complemento reverso, que rotularemos de $ \ bar {X} $ .

Suponha que $ X $ tenha um comprimento ímpar. Então, é da forma $ AbC $ , onde $ len (A) = len (C) = \ frac {len (X) -1} {2} $ , e $ len (b) = 1 $ .

Então

$ X = \ bar {X} \ implica AbC = \ overline {AbC} = \ bar {C} \ bar {b} \ bar {A} $ span>

E, portanto:

$ b = \ bar {b} $

( uma vez que $ len (A) = len (C) = len (\ bar {C})) $ . Mas isso é uma contradição, pois $ b $ é um único nucleotídeo e não pode ser igual ao seu complemento. Portanto, k-mers de comprimento ímpar não podem formar palíndromos.

Portanto, o comprimento de um k-mer que forma um palíndromo deve ser par.


2. Por que k-mers palindrômicos induzem loops próprios

Cada nó em um gráfico de Bruijn tradicional é uma string única, mas na maioria das implementações de bioinformática, cada par de k-1-mers complementares reversos é identificado como um nó único, por exemplo, para $ k = 6 $ :

A palíndromo k-mer (de $ k \ geq 2 $ ) tem a forma:

$ xAy $

onde $ len (A) = k-2 $ span>, $ x = \ bar {y} $ e $ A = \ bar {A} $ (possivelmente a string vazia).

Conseqüentemente, contribuirá com dois nós no gráfico de Bruijn:

  1. seu k-1-mer esquerdo $ xA $
  2. seu k-1-mer direito $ Ay $

E uma borda indo de 1 a 2.

Mas como este k-mer é palíndromo, $ xA = \ overline {Ay} $ e, portanto, esses dois nós são complementares-reversos e, portanto, o 'mesmo' nó e, portanto, essa aresta é um loop automático neste nó.


3. Por que os auto-loops são problemáticos?

Auto-loops (se ocorrerem em um nó com $ in \ _degree \ geq 2 $ e $ out \ _degree \ geq 1 $ ) aumenta o número de caminhos Eulerianos possíveis em um gráfico de Bruijn (ou mais especificamente, no componente conectado contendo este nó, que representa um contig , dos quais podem ser múltiplos), já que você tem um caminho Euleriano possível adicional para cada vez que você atravessa este nó.

Isso aumenta a ambigüidade na leitura do gráfico, pois cada Euleriano possível caminho é uma reconstrução extra possível da sequência completa.

Considere o exemplo:

enter image description here

Há apenas um caminho Euleriano possível:

  • $ ABCDBE $

No entanto, se incluirmos um loop self em $ B $ , que é visitado duas vezes acima, isso duplica para dois caminhos Eulerianos possíveis:

enter image description here

  • $ ABBCDBE $
  • $ ABCDBBE $

Dependendo de se atravessamos o auto-loop durante a primeira vez que alcançamos $ B $ , ou a segunda vez.

https://homolog.us/Tutorials/book4/p2.4.html "Os programas de montagem do genoma também evitam k, porque com k mesmo, muitos k-mers tornam-se complementos reversos de suas próprias sequências. ** Isso causa ambigüidades no especificidade de fita do gráfico. ** Portanto, valores k ímpares são preferidos. "
Boa resposta @ukemi. Demorei a compreender a conclusão do ponto 1, por isso acrescentei uma frase que teria me ajudado. Se você não gostar, você pode reverter a mudança, mas eu diria que um pequeno esclarecimento seria bom aí.
@KamilSJaron não se preocupe, quanto mais claro melhor - sim, tecnicamente eu também deveria ter mostrado existência para a implicação de que eles devem ser pares para seguir (em oposição a apenas não ímpar), mas mostrar a existência é trivial por meio de exemplo (por exemplo, AT, ATAT etc).


Estas perguntas e respostas foram traduzidas automaticamente do idioma inglês.O conteúdo original está disponível em stackexchange, que agradecemos pela licença cc by-sa 3.0 sob a qual é distribuído.
Loading...