A greedy, graph-based algorithm for the alignment of multiple homologous gene lists
A greedy, graph-based algorithm for the alignment of multiple homologous gene lists
复制标题
DOI：
10.1093/bioinformatics/btr008
复制
发表时间：
2011-03-15
期刊：
影响因子：
5.8
通讯作者：
Vandepoele, Klaas
中科院分区：
文献类型：
--
作者：
Fostier, Jan;Proost, Sebastian;Vandepoele, Klaas
动机：许多比较基因组学研究依赖于使用精确的比对工具对同源基因组区域的正确鉴定。在这种情况下，输入序列的字母表由完整的基因组成，而不是核苷酸或氨基酸。由于最优多序列比对在计算上不现实，通常采用渐进比对策略。然而，这种方法容易在早期成对比对步骤中传播比对误差，特别是在处理强烈分化的基因组区域时。在这篇文章中，我们提出了一种新的精确和高效的贪婪的，基于图的算法，用于多个同源基因组片段的比对，表示为有序的基因列表。结果：基于图结构的可证明性质，开发了几种启发式方法来解决由于基因复制和/或重排事件在不同基因组片段上发生的局部比对冲突。通过将拟南芥同源基因组片段的比对结果与采用渐进式比对方法和早期基于图的实现方法获得的比对结果进行比较，评估了算法的性能。特别是对于包含强烈分化片段的数据集，该方法实现了更高的比对精度，并且对于包括几十个真核生物基因组在内的大型数据集证明了足够快的比对速度。
Motivation: Many comparative genomics studies rely on the correct identification of homologous genomic regions using accurate alignment tools. In such case, the alphabet of the input sequences consists of complete genes, rather than nucleotides or amino acids. As optimal multiple sequence alignment is computationally impractical, a progressive alignment strategy is often employed. However, such an approach is susceptible to the propagation of alignment errors in early pairwise alignment steps, especially when dealing with strongly diverged genomic regions. In this article, we present a novel accurate and efficient greedy, graph-based algorithm for the alignment of multiple homologous genomic segments, represented as ordered gene lists.Results: Based on provable properties of the graph structure, several heuristics are developed to resolve local alignment conflicts that occur due to gene duplication and/or rearrangement events on the different genomic segments. The performance of the algorithm is assessed by comparing the alignment results of homologous genomic segments in Arabidopsis thaliana to those obtained by using both a progressive alignment method and an earlier graph-based implementation. Especially for datasets that contain strongly diverged segments, the proposed method achieves a substantially higher alignment accuracy, and proves to be sufficiently fast for large datasets including a few dozens of eukaryotic genomes.