关于全局序列比对。

On global sequence alignment.

作者信息

Huang X

机构信息

Department of Computer Science, Michigan Technological University, Houghton 49931.

出版信息

Comput Appl Biosci. 1994 Jun;10(3):227-35. doi: 10.1093/bioinformatics/10.3.227.

DOI:10.1093/bioinformatics/10.3.227

PMID:7922677

Abstract

We present a dynamic programming algorithm for computing a best global alignment of two sequences. The proposed algorithm is robust in identifying any of several global relationships between two sequences. The algorithm delivers a best alignment of two sequences in linear space and quadratic time. We also describe a multiple alignment algorithm based on the pairwise algorithm. Both algorithms have been implemented as portable C programs. Experimental results indicate that for a commonly used set of gap penalties, the new programs produce more satisfactory alignments on sequences of various lengths than some existing pairwise and multiple programs based on the dynamic programming algorithm of Needleman and Wunsch.

摘要

我们提出了一种用于计算两个序列最佳全局比对的动态规划算法。所提出的算法在识别两个序列之间的几种全局关系中的任何一种时都很稳健。该算法在线性空间和二次时间内给出两个序列的最佳比对。我们还描述了一种基于成对算法的多重比对算法。这两种算法都已实现为可移植的C程序。实验结果表明，对于一组常用的空位罚分，新程序在各种长度的序列上比一些基于Needleman和Wunsch动态规划算法的现有成对和多重程序产生更令人满意的比对。