Fast Identification of Approximately Matching Substrings
Fast Identification of Approximately Matching Substrings
复制标题
近似匹配子串的快速识别
DOI：
10.1007/3-540-58094-8_6
复制
发表时间：
1994
影响因子：
19.9
通讯作者：
A. Cobbs
中科院分区：
文献类型：
--
作者：
A. Cobbs
Let two strings S, T over a finite alphabet Σ be given, and let M be an arbitrary relation on Σ×Σ. Define an approximate match (x,y) of two length m subwords (substrings) x ⊑ S, y ⊑ T when M(x i ,y i , for all 1≤i≤m. A match implies all the local alignments (without insertions and deletions) which are pairings of specific occurrances of x and y. A match (x,y) is maximal if there exists no longer match (u, v) such that all of the local alignments implied by (x,y) are contained in a local alignment implied by (u,v). We give an efficient algorithm for finding all maximal matches between S and T. The algorithm runs in time bounded by the sum of the lengths of the maximal matches, at worst. O(¦Σ¦2n2). The main application is identifying homologous regions of protein sequences.
影响因子：
2.5
作者：
MCCREIGHT, EM
通讯作者：
MCCREIGHT, EM