Genome alignment with graph data structures: a comparison.
Genome alignment with graph data structures: a comparison.
复制标题
DOI：
10.1186/1471-2105-15-99
复制
发表时间：
2014-04-09
影响因子：
3
通讯作者：
Reinert K
中科院分区：
文献类型：
--
作者：
Kehr B;Trappe K;Holtgrewe M;Reinert K
快速、低成本测序的最新进展为研究完整的基因组序列提供了机会。多基因组比对的计算方法允许以综合的方式调查进化相关的基因组，为下游分析提供基础，如重排研究和系统发育推断。图已被证明是一个强大的工具，以应付复杂的基因组规模的序列比对。图形直观地表示基因组比对的所有方面的潜力导致了基于图形的基因组比对方法的发展。这些方法从一组局部比对构建图，并通过识别和去除指示比对中的错误的图子结构来导出基因组比对。我们比较常用的图的结构，在他们的能力，以表示对齐信息。我们描述了如何图可以相互转换，并确定和分类一个或多个图的图形子结构。基于以前的方法，我们编译了一个删除这些子结构的修改列表。我们发现，与反转和重复相关的对齐信息的关键片段在所有图的结构中是不可见的。如果我们忽略顶点或边标签，图的信息内容不同。尽管如此，许多想法在所有基于图的方法中是共享的。基于这些发现，我们概述了基于图的基因组比对的概念框架，可以帮助开发未来的基因组比对工具。
Recent advances in rapid, low-cost sequencing have opened up the opportunity to study complete genome sequences. The computational approach of multiple genome alignment allows investigation of evolutionarily related genomes in an integrated fashion, providing a basis for downstream analyses such as rearrangement studies and phylogenetic inference. Graphs have proven to be a powerful tool for coping with the complexity of genome-scale sequence alignments. The potential of graphs to intuitively represent all aspects of genome alignments led to the development of graph-based approaches for genome alignment. These approaches construct a graph from a set of local alignments, and derive a genome alignment through identification and removal of graph substructures that indicate errors in the alignment. We compare the structures of commonly used graphs in terms of their abilities to represent alignment information. We describe how the graphs can be transformed into each other, and identify and classify graph substructures common to one or more graphs. Based on previous approaches, we compile a list of modifications that remove these substructures. We show that crucial pieces of alignment information, associated with inversions and duplications, are not visible in the structure of all graphs. If we neglect vertex or edge labels, the graphs differ in their information content. Still, many ideas are shared among all graph-based approaches. Based on these findings, we outline a conceptual framework for graph-based genome alignment that can assist in the development of future genome alignment tools.
登录
查看更多内容
影响因子：
5.8
作者：
Fostier, Jan;Proost, Sebastian;Vandepoele, Klaas
通讯作者：
Vandepoele, Klaas
影响因子：
5.6
作者：
Gotoh, O
通讯作者：
Gotoh, O
影响因子：
7
作者：
Alekseyev, Max A.;Pevzner, Pavel A.
通讯作者：
Pevzner, Pavel A.
影响因子：
10.7
作者：
Blackburne, Benjamin P.;Whelan, Simon
通讯作者：
Whelan, Simon
DOI：
10.1007/978-1-61779-582-4_15
发表时间：
2012-01-01
期刊：
EVOLUTIONARY GENOMICS: STATISICAL AND COMPUTATIONAL METHODS, VOL 1
影响因子：
--
作者：
El-Mabrouk, Nadia;Sankoff, David
通讯作者：
Sankoff, David