Local sequence alignments with monotonic gap penalties.
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 alg...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
1999
|
| _version_ | 1826267066869481472 |
|---|---|
| author | Mott, R |
| author_facet | Mott, R |
| author_sort | Mott, R |
| collection | OXFORD |
| description | 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 local 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) >/= g(k-1). The running time of the algorithm is dependent on the scoring scheme; if the expected score of an alignment between random, unrelated sequences of lengths m, n is proportional to log mn, 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 can dramatically increase the probability of detecting a similarity containing a long gap. AVAILABILITY: The source code is available to academic collaborators under licence. |
| first_indexed | 2024-03-06T20:48:31Z |
| format | Journal article |
| id | oxford-uuid:36c44cee-36b8-4342-9c22-8249ab670377 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T20:48:31Z |
| publishDate | 1999 |
| record_format | dspace |
| spelling | oxford-uuid:36c44cee-36b8-4342-9c22-8249ab6703772022-03-26T13:39:56ZLocal sequence alignments with monotonic gap penalties.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:36c44cee-36b8-4342-9c22-8249ab670377EnglishSymplectic Elements at Oxford1999Mott, RMOTIVATION: 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 local 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) >/= g(k-1). The running time of the algorithm is dependent on the scoring scheme; if the expected score of an alignment between random, unrelated sequences of lengths m, n is proportional to log mn, 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 can dramatically increase the probability of detecting a similarity containing a long gap. AVAILABILITY: The source code is available to academic collaborators under licence. |
| spellingShingle | Mott, R Local sequence alignments with monotonic gap penalties. |
| title | Local sequence alignments with monotonic gap penalties. |
| title_full | Local sequence alignments with monotonic gap penalties. |
| title_fullStr | Local sequence alignments with monotonic gap penalties. |
| title_full_unstemmed | Local sequence alignments with monotonic gap penalties. |
| title_short | Local sequence alignments with monotonic gap penalties. |
| title_sort | local sequence alignments with monotonic gap penalties |
| work_keys_str_mv | AT mottr localsequencealignmentswithmonotonicgappenalties |