title: Local sequence alignments with monotonic gap penalties.
abstract: BACKGROUND
  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.
  
  
  BACKGROUND
  The source code is available to academic collaborators under licence.
authors.affiliation: SmithKline-Beecham Pharmaceuticals R & D, New Frontiers Science Park (North),3rd Avenue, Harlow CM19 5AW, UK. Richard.Mott@well.ox.ac.uk
authors.forename: R
authors.initials: R
authors.lastname: Mott
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D005069:Evaluation Studies as Topic; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods* / Q000706:statistics & numerical data; D012984:Software