Questão:
Como fazer uma distinção entre o gráfico "clássico" de Bruijn e aquele descrito nos artigos da NGS?
Leo Martins
2017-05-19 15:32:45 UTC
view on stackexchange narkive permalink

Em Ciência da Computação, um gráfico De Bruijn tem (1) m ^ n vértices representando todas as sequências possíveis de comprimento n sobre símbolos m e (2) arestas direcionadas conectando nós que diferem por um deslocamento de elementos n-1 (o sucessor tendo o novo elemento à direita).

No entanto, em Bioinformática enquanto a condição (2) é preservada, o que é chamado de gráfico de De Bruijn parece não respeitar a condição (1). Em alguns casos, o gráfico não se parece em nada com um gráfico de Bruijn (por exemplo, http://genome.cshlp.org/content/18/5/821.full).

Portanto, minha pergunta é, se eu quiser deixar explícito que estou usando a interpretação bioinformática de um gráfico de Bruijn, há um termo para isso? Algo como "gráfico de Bruijn simplificado", "projeção de um gráfico de Bruijn" ou "gráfico de k-mers vizinhos"? Há algum artigo fazendo essa distinção ou eu entendi tudo errado?

Basicamente, a condição 1 significa que mesmo vértices sem arestas devem estar presentes no gráfico, certo?
Quer dizer, eu me pergunto se alguma implementação não bioinformática do gráfico De Bruijn realmente os armazena, uma vez que eles não carregam nenhuma informação útil.
Há mais uma diferença nos gráficos De Bruijn usados ​​para a montagem do genoma - as bordas são ponderadas.
Olá, @Slim re. Q1, acredito que os gráficos de de Bruijn estão conectados (um componente). Você pode construí-los fornecendo `m` e` n` (http://mathworld.wolfram.com/deBruijnGraph.html). Q2: sim, as implementações não precisam de todos os nós; O grafo de Bruijn é uma entidade abstrata, uma estrutura combinatória, como um "grafo completo". Mas se meu gráfico muito importante perder algumas arestas (b / c inútil), não posso chamá-lo de "completo". Isso não o torna menos importante, aliás! Q3: isso é verdade! Obrigado por editar a pergunta.
Trzy respostas:
#1
+7
Leo Martins
2017-05-23 01:33:56 UTC
view on stackexchange narkive permalink

Vários artigos fizeram essa distinção, e alguns realmente usam termos diferentes para distingui-los. Por exemplo, Kazaux et al. (2016) reconhecem que:

Essas restrições favorecem o uso de uma versão do de Bruijn Graph (dBG) dedicado à montagem do genoma - uma versão que difere da estrutura combinatória inventada por NG de Bruijn.

Kingsford et al. (2010) também reconhecem a distinção:

Observe que esta definição de um gráfico de de Bruijn difere da definição tradicional descrita na literatura matemática na década de 1940, que exige que o gráfico contenha todas as strings de comprimento k que podem ser formadas a partir de um alfabeto (em vez de apenas aquelas strings presentes no genoma).

A referência mais antiga que encontrei para um termo específico para se referir à estrutura relacionada à montagem é Skiena e Sundaram (1995), onde eles chamam de subgrafo do digrafo de de Bruijn . Mais tarde, em 2002, Błażewicz et al. irá referir-se a ele como um subgrafo induzido de Bruijn . O termo subgrafo de Bruijn também é formalmente definido na tese de Quitzau (2009). Lá, e também no artigo ( Quitzau e Stoye, 2008), os autores descrevem o gráfico de sequência como uma modificação do subgrafo esparso de Bruijn (comumente usado em problemas de montagem) , onde caminhos sem ramificação são substituídos por um único vértice. O termo gráfico esparso de Bruijn também é usado por Chauve et al. (2013).

Outro termo que encontrei foi gráfico de palavras , descrito por Malde et al. (2005) e por Heath e Pati (2007) como um subgráfico ou como uma generalização de um gráfico de Bruijn. Rødland (2013) resume alguns dos termos usados ​​para esta estrutura de dados:

A estrutura de dados é melhor compreendida em termos da representação do subgrafo de de Bruijn de S [k]. (...) Alguns autores podem se referir a isso como um gráfico de palavras, ou mesmo apenas um gráfico de Bruijn.

Embora possamos reconhecer que a distinção não é muito relevante, a questão é perguntando especificamente sobre a situação em que se deseja fazer tal distinção.

Como muitos jornais e eu dissemos, o gráfico de assembly de Bruijn é apenas um subgrafo do gráfico de Bruijn completo. Qualquer pessoa que diga o contrário deixa de reconhecer essa relação simples. "Gráfico de sequência" é muito geral e usado em outro contexto (por exemplo, gráfico de montagem de sequência). "Gráfico esparso de Bruijn" é mais apropriado para um gráfico construído pulando alguns k-mers em leituras (por exemplo, em montador esparso). O gráfico de palavras acíclicas direcionadas (DAWG) é um conceito pré-existente, pelo menos datado dos anos 80, o que torna o "gráfico de palavras" ambíguo também. As pessoas deveriam parar de inventar novos nomes para um subgrafo.
Pevzner fez um trabalho seminal usando os gráficos de Bruijn na montagem (http://www.pnas.org/content/98/17/9748.full) e emendas alternativas (https://www.ncbi.nlm.nih.gov/ pubmed / 12169546)
#2
+4
holmrenser
2017-05-19 16:07:00 UTC
view on stackexchange narkive permalink

Além do gráfico De Bruijn regular conforme descrito na wikipedia, algumas implementações em bioinformática apresentam processamento adicional. Acho que a principal razão pela qual a figura 1 no artigo que você vinculou (em relação ao montador do genoma Velvet) é ligeiramente diferente é que um nó representa uma série de k-mers sobrepostos . Para visualizar isso como um gráfico de De Bruin mais clássico, você teria que conectar os k-mers representados acima dos nós. A legenda ao lado da figura um descreve o processamento de forma bastante clara.

De acordo com sua última pergunta: Não acho que haja uma 'interpretação bioinformática de um gráfico de De Bruijn'. Existem diferentes implementações, todas com especificidades. Portanto, seria melhor se referir à implementação real.

Como um exemplo: este é um bom artigo sobre como construir um gráfico de De Bruijn pan-genoma de vários genomas simultaneamente .

Mas uma "implementação" de um gráfico de Bruijn que não inclui todos os k-mers não é mais um gráfico de Bruijn (no sentido original), certo? Se a implementação não satisfizer a condição (1) acima, eu me pergunto se há outro nome (ou um qualificador) sendo usado.
Tenho certeza de que todos os k-mers originais estão presentes de alguma forma.
#3
+3
user172818
2017-05-19 19:14:34 UTC
view on stackexchange narkive permalink

Vamos primeiro assumir que o DNA tem apenas uma fita. Um gráfico de montagem de Bruijn é um subgráfico de um gráfico de Bruijn completo. Ele contém um vértice u se u for um k-mer em leituras; ele contém uma aresta u-> v, se uev são k-mers adjacentes em uma leitura. Alternativamente, notamos que uma aresta u-> v é representada por a (k + 1) -mer. Um grafo de Bruijn assembly pode ser considerado uma aresta do subgrafo induzida por todos os (k + 1) -mers em leituras - de fato, alguns montadores tomam a lista de (k + 1) -mer como uma representação sucinta dos grafos de de Bruijn.

O DNA possui duas fitas. Precisamos apenas induzir um gráfico de montagem de Bruijn de todos os (k + 1) -mers e seu complemento reverso. Ainda é um subgrafo de um grafo de Bruijn completo.

Porque um grafo de Bruijn assembly é apenas um subgrafo. Não é necessário dar um novo nome.

PS: Excluí minha resposta anterior, pois não era o que você estava pedindo com base em seus comentários. Fiquei confuso com sua menção a veludo. O Velvet usa uma representação equivalente, mas incomum, dos gráficos de de Bruijn, o que complica sua pergunta.



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