快速最优比对
Fast optimal alignment.
作者信息
Fickett J W
出版信息
Nucleic Acids Res. 1984 Jan 11;12(1 Pt 1):175-9. doi: 10.1093/nar/12.1part1.175.
Abstract
We show how to speed up sequence alignment algorithms of the type introduced by Needleman and Wunsch (and generalized by Sellers and others). Faster alignment algorithms have been introduced, but always at the cost of possibly getting sub-optimal alignments. Our modification results in the optimal alignment still being found, often in 1/10 the usual time. What we do is reorder the computation of the usual alignment matrix so that the optimal alignment is ordinarily found when only a small fraction of the matrix is filled. The number of matrix elements which have to be computed is related to the distance between the sequences being aligned; the better the optimal alignment, the faster the algorithm runs.
摘要
我们展示了如何加速由Needleman和Wunsch提出（并由Sellers等人推广）的那种类型的序列比对算法。虽然已经引入了更快的比对算法，但总是以可能得到次优比对为代价。我们的修改使得仍然能够找到最优比对，而且通常所需时间仅为原来的十分之一。我们所做的是重新安排常规比对矩阵的计算顺序，这样通常在矩阵只填充了一小部分时就能找到最优比对。必须计算的矩阵元素数量与要比对的序列之间的距离有关；最优比对越好，算法运行得就越快。
相似文献
1
Fast optimal alignment.快速最优比对
Nucleic Acids Res. 1984 Jan 11;12(1 Pt 1):175-9. doi: 10.1093/nar/12.1part1.175.
2
Fast, statistically based alignment of amino acid sequences on the base of diagonal fragments of DOT-matrices.基于点阵矩阵对角片段的氨基酸序列快速统计比对。
Comput Appl Biosci. 1992 Dec;8(6):529-34. doi: 10.1093/bioinformatics/8.6.529.
3
Exact and complete short-read alignment to microbial genomes using Graphics Processing Unit programming.使用图形处理单元编程实现微生物基因组的精确和完整短读序列比对。
Bioinformatics. 2011 May 15;27(10):1351-8. doi: 10.1093/bioinformatics/btr151. Epub 2011 Mar 30.
4
Alignment of nucleotide or amino acid sequences on microcomputers, using a modification of Sellers' (1974) algorithm which avoids the need for calculation of the complete distance matrix.利用对塞勒斯（1974年）算法的一种改进，在微型计算机上对核苷酸或氨基酸序列进行比对，该改进避免了计算完整距离矩阵的需要。
Comput Methods Programs Biomed. 1985 Oct;21(1):3-10. doi: 10.1016/0169-2607(85)90057-4.
5
Comparative biosequence metrics.比较生物序列度量
J Mol Evol. 1981;18(1):38-46. doi: 10.1007/BF01733210.
6
Further improvement in methods of group-to-group sequence alignment with generalized profile operations.使用广义轮廓操作的组间序列比对方法的进一步改进。
Comput Appl Biosci. 1994 Jul;10(4):379-87. doi: 10.1093/bioinformatics/10.4.379.
7
A method for detecting distant evolutionary relationships between protein or nucleic acid sequences in the presence of deletions or insertions.一种在存在缺失或插入的情况下检测蛋白质或核酸序列之间远距离进化关系的方法。
J Mol Evol. 1978 Jun 20;11(2):143-61. doi: 10.1007/BF01733890.
8
Sigma: multiple alignment of weakly-conserved non-coding DNA sequence.西格玛：弱保守非编码DNA序列的多重比对
BMC Bioinformatics. 2006 Mar 16;7:143. doi: 10.1186/1471-2105-7-143.
9
Fast, optimal alignment of three sequences using linear gap costs.使用线性空位罚分对三个序列进行快速、最优比对。
J Theor Biol. 2000 Dec 7;207(3):325-36. doi: 10.1006/jtbi.2000.2177.
10
A novel randomized iterative strategy for aligning multiple protein sequences.一种用于比对多条蛋白质序列的新型随机迭代策略。
Comput Appl Biosci. 1991 Oct;7(4):479-84. doi: 10.1093/bioinformatics/7.4.479.
引用本文的文献
1
Releasing the Kraken.释放海怪。
Front Bioinform. 2021 Dec 6;1:808003. doi: 10.3389/fbinf.2021.808003. eCollection 2021.
2
smsMap: mapping single molecule sequencing reads by locating the alignment starting positions.smsMap：通过定位比对起始位置来对单分子测序reads 进行映射。
BMC Bioinformatics. 2020 Aug 4;21(1):341. doi: 10.1186/s12859-020-03698-w.
3
A short note on dynamic programming in a band.关于带动态规划的简要说明。
BMC Bioinformatics. 2018 Jun 15;19(1):226. doi: 10.1186/s12859-018-2228-9.
4
Secure approximation of edit distance on genomic data.基因组数据编辑距离的安全近似值。
BMC Med Genomics. 2017 Jul 26;10(Suppl 2):41. doi: 10.1186/s12920-017-0279-9.
5
Reticular alignment: a progressive corner-cutting method for multiple sequence alignment.网状排列：一种渐进式的多重序列比对角切割方法。
BMC Bioinformatics. 2010 Nov 23;11:570. doi: 10.1186/1471-2105-11-570.
6
Sequence similarity ('homology') searching for molecular biologists.面向分子生物学家的序列相似性（“同源性”）搜索。
Bull Math Biol. 1985;47(4):437-74. doi: 10.1007/BF02460006.
7
An efficient string matching algorithm with k differences for nucleotide and amino acid sequences.一种针对核苷酸和氨基酸序列的具有k个差异的高效字符串匹配算法。
Nucleic Acids Res. 1986 Jan 10;14(1):31-46. doi: 10.1093/nar/14.1.31.
8
Sequence comparison with concave weighting functions.使用凹加权函数进行序列比较。
Bull Math Biol. 1988;50(2):97-120. doi: 10.1007/BF02459948.
9
Fast analysis of DNA and protein sequence on Apple IIe: restriction sites search, alignment of short sequence and dot matrix analysis.在苹果IIe计算机上对DNA和蛋白质序列进行快速分析：限制酶切位点搜索、短序列比对及点阵分析。
Nucleic Acids Res. 1986 Jan 10;14(1):583-90. doi: 10.1093/nar/14.1.583.
10
A comprehensive package for DNA sequence analysis in FORTRAN IV for the PDP-11.一个用于PDP - 11的FORTRAN IV语言的DNA序列分析综合程序包。
Nucleic Acids Res. 1986 Jan 10;14(1):239-54. doi: 10.1093/nar/14.1.239.
本文引用的文献
1
Rapid similarity searches of nucleic acid and protein data banks.核酸和蛋白质数据库的快速相似性搜索。
Proc Natl Acad Sci U S A. 1983 Feb;80(3):726-30. doi: 10.1073/pnas.80.3.726.
2
A general method applicable to the search for similarities in the amino acid sequence of two proteins.一种适用于寻找两种蛋白质氨基酸序列相似性的通用方法。
J Mol Biol. 1970 Mar;48(3):443-53. doi: 10.1016/0022-2836(70)90057-4.
Zotero 插件