Locally optimal subalignments using nonlinear similarity functions (Q1090289)

This paper gives algorithms for finding similar subsequences in two sequences. In biology, nonlinear similarity costs are often better than linear costs in distinguishing ''interesting'' subalignments from those due to chance. The new algorithms in this paper, unlike previous algorithms, can use very general similarity costs as selection criteria. The paper, though unsuitable as an introduction to the problem of sequence subalignments, gives a comprehensive terminology and set of references. It lists and discusses the selection of appropriate biological similarity costs at length. The paper gives a thorough explanation of the algorithms themselves, along with their time and storage complexities. The main practical contribution is an algorithm CC-1, which gives very good subalignments from two sequences of length M and N in time O(MN).