THE MULTIPLE SEQUENCE ALIGNMENT PROBLEM IN BIOLOGY
THE MULTIPLE SEQUENCE ALIGNMENT PROBLEM IN BIOLOGY
复制标题
DOI：
10.1137/0148063
复制
发表时间：
1988-10-01
影响因子：
1.9
通讯作者：
LIPMAN, D
中科院分区：
文献类型：
--
作者：
CARRILLO, H;LIPMAN, D
对有限字母表中字符序列的研究和比较与科学的各个领域有关，尤其是分子生物学。序列相似性的度量包括考虑不同可能的序列比对，以找到序列间“距离”最小的最优序列比对。通过将晶格中的路径与每个对齐方式相关联，可以将几何洞察力带入寻找最佳对齐方式的问题中。这个问题可以通过应用动态规划算法来解决。然而，随着要比较的序列的数量（即要比较的序列的平均长度）的增加，计算量会迅速增加。本文证明了任意选择的排列的度量的知识可以与来自成对排列的信息相结合，从而大大限制所考虑的晶格区域的大小。这种减少意味着执行动态规划优化过程所需的计算和内存空间更少。观测结果还提出了多重对准问题的新变体。
The study and comparison of sequences of characters from a finite alphabet is relevant to various areas of science, notably molecular biology. The measurement of sequence similarity involves the consideration of the different possible sequence alignments in order to find an optimal one for which the “distance” between sequences is minimum. By associating a path in a lattice to each alignment, a geometric insight can be brought into the problem of finding an optimal alignment. This problem can then be solved by applying a dynamic programming algorithm. However, the computational effort grows rapidly with the numberNof sequences to be compared, wherelis the mean length of the sequences to be compared).It is proved here that knowledge of the measure of an arbitrarily chosen alignment can be used in combination with information from the pairwise alignments to considerably restrict the size of the region of the lattice in consideration. This reduction implies fewer computations and less memory space needed to carry out the dynamic programming optimization process. The observations also suggest new variants of the multiple alignment problem.