Local sequence alignments with monotonic gap penalties
Local sequence alignments with monotonic gap penalties
复制标题
DOI：
10.1093/bioinformatics/15.6.455
复制
发表时间：
1999-06-01
期刊：
影响因子：
5.8
通讯作者：
Mott, R
中科院分区：
文献类型：
--
作者：
Mott, R
Motivation: Sequence alignments obtained using affine gap penalties are not always biologically correct, because the insertion of long gaps is over-penalised. There is a need for an efficient algorithm which can find local alignments using non-linear gap penalties.Results: A dynamic programming algorithm is described which computes optimal focal sequence alignments for arbitrary, monotonically increasing gap penalties, i.e. where the cost g(k) of inserting a gap of k symbols is such that g(k) greater than or equal to g(k - 1). The running time of the algorithm is dependent on the scoring scheme; if the expected score of art alignment between random, unrelated sequences of lengths m, n is proportional to logmn, then with one exception, the algorithm has expected running time O(mn). Elsewhere, the running time is no greater than O(mn(m + n)). Optimisations are described which appear to reduce the worst-case run-time to O(mn) in many cases. We show how using a non-affine gap penalty cart dramatically increase the probability of detecting a similarity containing a long gap.Availability: The source code is available to academic collaborators under licence.
