A versatile divide and conquer technique for optimal string alignment

https://doi.org/10.1016/S0020-0190(99)00053-8Get rights and content

Abstract

Common string alignment algorithms such as the basic dynamic programming algorithm (DPA) and the time efficient Ukkonen algorithm use quadratic space to determine an alignment between two strings. In this paper we present a technique that can be applied to these algorithms to obtain an alignment using only linear space, while having little or no effect on the time complexity. This new technique has several advantages over previous methods for determining alignments in linear space, such as: simplicity, the ability to use essentially the same technique when using different cost functions, and the practical advantage of easily being able to trade available memory for running time.

References (0)

Cited by (11)

  • Engineering a software tool for gene structure prediction in higher organisms

    2005, Information and Software Technology
    Citation Excerpt :

    ii) The main bottleneck of GenomeThreader is still the computation of spliced alignments. We are planning to implement a linear space spliced alignment algorithm utilizing techniques similar to Ref. [16]. Furthermore, we hope to improve the speed of the spliced alignment algorithm by careful code level optimization. (

  • Diploid alignments and haplotyping

    2015, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
  • An novel method of protein secondary structure prediction based on compound pyramid model

    2010, Proceedings - 2010 7th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2010
View all citing articles on Scopus
View full text