Improved Approximation Algorithms for Tree Alignment

✍ Scribed by Lusheng Wang; Dan Gusfield

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 251 KB
• Volume: 25
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1997.0882

✦ Synopsis

Multiple sequence alignment is a task at the heart of much of current computaw x tional biology 4 . Several different objective functions have been proposed to formalize the task of multiple sequence alignment, but efficient algorithms are lacking in each case. Thus multiple sequence alignment is one of the most critical, essentially unsolved problems in computational biology. In this paper we consider one of the more compelling objective functions for multiple sequence alignment, w x formalized as the tree alignment problem. Previously in 13 , a ratio-two approxima-Ž tion method was developed for tree alignment, which ran in cubic time as a . function of the number of fixed length strings to be aligned , along with a Ž . polynomial time approximation scheme PTAS for the problem. However, the w x PTAS in 13 had a running time which made it impractical to reduce the Ž performance ratio much below two for small size biological sequences 100 charac-. ters long . In this paper we first develop a ratio-two approximation algorithm which runs in quadratic time, and then use it to develop a PTAS which has a better performance ratio and a vastly improved worst case running time compared to the w x scheme in 13 for the case where the given tree is a regular deg-ary tree. With the new approximation scheme, it is now practical to guarantee a ratio of 1.583 for strings of lengths 200 characters or less.