.png){kind=icon}
返回
Faster algorithms for optimal multiple sequence alignment based on pairwise comparisons
.png){kind=icon}
OA
AI
DOI：10.1109/TCBB.2006.53.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Multiple Sequence Alignment (MSA) is one of the most fundamental problems in computational molecular biology. The running time of the best known scheme for finding an optimal alignment, based on dynamic programming, increases exponentially with the number of input sequences. Hence, many heuristics were suggested for the problem. We consider a version of the MSA problem where the goal is to find an optimal alignment in which matches are restricted to positions in predefined matching segments. We present several techniques for making the dynamic programming algorithm more efficient, while still finding an optimal solution under these restrictions. We prove that it suffices to find an optimal alignment of the predefined sequence segments, rather than single letters, thereby reducing the input size and thus improving the running time. We also identify shortcuts that expedite the dynamic programming scheme. Empirical study shows that, taken together, these observations lead to an improved running time over the basic dynamic programming algorithm by 4 to 12 orders of magnitude, while still obtaining an optimal solution. Under the additional assumption that matches between segments are transitive, we further improve the running time for finding the optimal solution by restricting the search space of the dynamic programming algorithm.
Keyword:
multiple sequence alignment
algorithms
dynamic programming
shortest path
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
I
IF:
3.4
论文数:
3.3K
被引数:
6.4K
机构
暂无机构信息
引用论文
.png){kind=icon}
β-Sitosterol Prevents Lipid Peroxidation and Improves Antioxidant Status and Histoarchitecture in Rats with 1,2-Dimethylhydrazine-Induced Colon Cancerβ-谷甾醇可防止脂质过氧化并改善1，2-二甲基肼诱导的结肠癌大鼠的抗氧化状态和组织结构
PREAI
分享收藏分享收藏
查看更多内容