一种针对核苷酸和氨基酸序列的具有k个差异的高效字符串匹配算法。
An efficient string matching algorithm with k differences for nucleotide and amino acid sequences.
作者信息
Landau G M, Vishkin U, Nussinov R
出版信息
Nucleic Acids Res. 1986 Jan 10;14(1):31-46. doi: 10.1093/nar/14.1.31.
Abstract
There are a few algorithms designed to solve the problem of the optimal alignment of one sequence, the pattern, of length m, with another, longer sequence the text, of length n. These algorithms allow mismatches, deletions and insertions. Algorithms to date run in O(mn) time. Let us define an integer, k, which is the maximal number of differences allowed. We present a simple algorithm showing that sequences can be optimally aligned in O(k2n) time. For long sequences the gain factor over the currently used algorithms is very large.
摘要
有一些算法旨在解决长度为m的一个序列（模式）与另一个更长的长度为n的序列（文本）的最优比对问题。这些算法允许错配、删除和插入。迄今为止的算法运行时间为O(mn)。我们定义一个整数k，它是允许的最大差异数。我们提出一种简单算法，表明序列可以在O(k²n)时间内进行最优比对。对于长序列，相对于当前使用的算法，增益因子非常大。
相似文献
1
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.
2
An efficient string matching algorithm with K substitutions for nucleotide and amino acid sequences.一种针对核苷酸和氨基酸序列的具有K个替换的高效字符串匹配算法。
J Theor Biol. 1987 Jun 21;126(4):483-90. doi: 10.1016/s0022-5193(87)80153-4.
3
Locating alignments with k differences for nucleotide and amino acid sequences.寻找核苷酸和氨基酸序列中存在k个差异的比对。
Comput Appl Biosci. 1988 Mar;4(1):19-24. doi: 10.1093/bioinformatics/4.1.19.
4
Approximate matching of regular expressions.正则表达式的近似匹配。
Bull Math Biol. 1989;51(1):5-37. doi: 10.1007/BF02458834.
5
On the application of integer arithmetic in nucleotide sequence analysis.整数运算在核苷酸序列分析中的应用
Comput Appl Biosci. 1995 Oct;11(5):567-9.
6
libFLASM: a software library for fixed-length approximate string matching.libFLASM：一个用于固定长度近似字符串匹配的软件库。
BMC Bioinformatics. 2016 Nov 10;17(1):454. doi: 10.1186/s12859-016-1320-2.
7
Improving sequence-matching algorithms by working from both ends.通过从两端入手改进序列匹配算法。
J Mol Biol. 1985 Jan 5;181(1):137-8. doi: 10.1016/0022-2836(85)90331-6.
8
Alignment of three biological sequences with an efficient traceback procedure.使用高效回溯程序对三个生物序列进行比对。
J Theor Biol. 1986 Aug 7;121(3):327-37. doi: 10.1016/s0022-5193(86)80112-6.
9
Optimal sequence alignment allowing for long gaps.允许长间隙的最优序列比对。
Bull Math Biol. 1990;52(3):359-73. doi: 10.1007/BF02458577.
10
On pattern matching with mismatches and few don't cares.关于带有不匹配项和少量无关项的模式匹配。
Inf Process Lett. 2017 Feb;118:78-82. doi: 10.1016/j.ipl.2016.10.003. Epub 2016 Oct 27.
引用本文的文献
1
Pioneer in Molecular Biology: Conformational Ensembles in Molecular Recognition, Allostery, and Cell Function.分子生物学先驱：分子识别、别构效应及细胞功能中的构象集合体
J Mol Biol. 2025 Jun 1;437(11):169044. doi: 10.1016/j.jmb.2025.169044. Epub 2025 Feb 25.
2
RNA structure prediction using positive and negative evolutionary information.利用正向和负向进化信息进行 RNA 结构预测。
PLoS Comput Biol. 2020 Oct 30;16(10):e1008387. doi: 10.1371/journal.pcbi.1008387. eCollection 2020 Oct.
3
Edlib: a C/C ++ library for fast, exact sequence alignment using edit distance.Edlib：一个使用编辑距离进行快速、精确序列比对的C/C++库。
Bioinformatics. 2017 May 1;33(9):1394-1395. doi: 10.1093/bioinformatics/btw753.
4
GOSSIP: a method for fast and accurate global alignment of protein structures.闲话：一种快速准确的蛋白质结构全局比对方法。
Bioinformatics. 2011 Apr 1;27(7):925-32. doi: 10.1093/bioinformatics/btr044. Epub 2011 Feb 3.
5
ASEtrap: a biological method for speeding up the exploration of spliceomes.ASEtrap：一种加速剪接体探索的生物学方法。
Genome Res. 2006 Jun;16(6):776-86. doi: 10.1101/gr.5063306. Epub 2006 May 8.
6
Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors.形式语言理论与DNA：对特定重组行为生成能力的分析
Bull Math Biol. 1987;49(6):737-59. doi: 10.1007/BF02481771.
本文引用的文献
1
Pattern recognition in genetic sequences.基因序列中的模式识别。
Proc Natl Acad Sci U S A. 1979 Jul;76(7):3041. doi: 10.1073/pnas.76.7.3041.
2
Enhanced graphic matrix analysis of nucleic acid and protein sequences.核酸和蛋白质序列的增强图形矩阵分析
Proc Natl Acad Sci U S A. 1981 Dec;78(12):7665-9. doi: 10.1073/pnas.78.12.7665.
3
Pattern recognition in nucleic acid sequences. I. A general method for finding local homologies and symmetries.核酸序列中的模式识别。I. 寻找局部同源性和对称性的通用方法。
Nucleic Acids Res. 1982 Jan 11;10(1):247-63. doi: 10.1093/nar/10.1.247.
4
Fast optimal alignment.快速最优比对
Nucleic Acids Res. 1984 Jan 11;12(1 Pt 1):175-9. doi: 10.1093/nar/12.1part1.175.
5
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.
6
An efficient code searching for sequence homology and DNA duplication.一种用于搜索序列同源性和DNA重复的高效编码。
J Theor Biol. 1983 Jan 21;100(2):319-28. doi: 10.1016/0022-5193(83)90355-7.
7
Efficient algorithms for folding and comparing nucleic acid sequences.用于折叠和比较核酸序列的高效算法。
Nucleic Acids Res. 1982 Jan 11;10(1):197-206. doi: 10.1093/nar/10.1.197.
8
Fast algorithm for predicting the secondary structure of single-stranded RNA.预测单链RNA二级结构的快速算法
Proc Natl Acad Sci U S A. 1980 Nov;77(11):6309-13. doi: 10.1073/pnas.77.11.6309.
9
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.
10
Estimation of secondary structure in ribonucleic acids.核糖核酸二级结构的估算
Nature. 1971 Apr 9;230(5293):362-7. doi: 10.1038/230362a0.
Zotero 插件