Near optimal multiple alignment within a band in polynomial time
Ming Li, Bin Ma, Lusheng Wang · 2000
Multiple sequence alignment is one of the most important problems in computational biology.Because of its notorious difficulties, aligning sequences within a constant band is a popular practice in bioinformatics with good results [17; 13; 14; 15; 1; 3; 6; 20; 18].However, the problem is still NP-hard for multiple sequences.In this paper, we present polynomial time approximation schemes (PTAS) for multiple sequence alignment within a constant band, tinder standard models of SP alignment and consensus (star) alignment.The algorithms work for very general score schemes.In order to prove our main results, we also present a PTAS for SP alignment and a PTAS for consensus alignment, allowing only constant number of insertion and deletion gaps (of arbitrary length) per sequence on the average.