On approximation algorithms for local multiple alignment
Tatsuya Akutsu, Hiroki Arimura, Shinichi Shimozono · 2000
This paper studies the local multiple alignment problem, which is also known as the general consensus patterns problem. Local multiple alignment is, given protein or DNA sequences, to locate a region (i.e., a substring) of fixed length from each sequence so that the score determined from the set of regions is optimized. We consider the following scoring schemes. the score indicating the average information content, the score defined by Li et al, and the sum-of-pairs score