On approximation algorithms for local multiple alignment

作者：Tatsuya Akutsu, Hiroki Arimura, Shinichi Shimozono · 年份：2000 · DOI：10.1145/332306.332311 · 被引用次数：37 · 研究领域：Algorithms and Data Compression、Complexity and Algorithms in Graphs、Machine Learning and Algorithms

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