UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Local sequence alignments with monotonic gap penalties.

Mott, R; (1999) Local sequence alignments with monotonic gap penalties. Bioinformatics , 15 (6) pp. 455-462. 10.1093/bioinformatics/15.6.455.

Full text not available from this repository.

Abstract

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.

Type: Article
Title: Local sequence alignments with monotonic gap penalties.
Location: England
DOI: 10.1093/bioinformatics/15.6.455
Keywords: Algorithms, Computational Biology, Evaluation Studies as Topic, Sensitivity and Specificity, Sequence Alignment, Software
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences > Div of Biosciences
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences > Div of Biosciences > Genetics, Evolution and Environment
URI: http://discovery.ucl.ac.uk/id/eprint/1562217
Downloads since deposit
0Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item