Finding similar regions in many strings
Ming Li, Bin Ma, Lusheng Wang · 1999
Algorithms for finding similar, or highly conserved, regions in a group of sequences are at the core of many molecular biology problems.We solve three main open questions in this area.Assume that we are given n DNA sequences 81,., an.The Consensus Patterns problem, which has been widely studied in bioinformatics research [26,16,12,25,4, 6, 15, 22, 24, 271, in its simplest form, asks for a region of length L in each ai, and a median string s of length L so that the total Hamming distance from B to these regions is minimized.We show the problem is NPhard and give a polynomial time approximation scheme (PTAS) for it.We also give a PTAS for the problem under the original measure of [26,16,12, 251.As an interesting application of OUT analysis, we further obtain a PTAS for a restricted (but still NP-hard) version of the important star alignment problem allowing at most constant number of gaps, each of arbitrary length, in each sequence.The Closest String problem [Z, 3, 7, 9, 181 asks for the smallest d and a string d which is within Hamming distance d to each a;.The problem is NP-hard [7, 181.[3] gives a polynomial time algorithm for constant d.For super-logarithmic d, [Z, 91 give efficient approximation algorithms using linear program relaxation techniques.The best polynomial time approximation has ratio $ for all d, given by [18] ([9] also independently claimed the $ ratio but only for super-logarithmic d).We settle the problem with a PTAS.We then give the fist nontrivial better-than-2 approximation with ratio 2 -& for the more eluive Closest Substring problem [IS]: find a string d of length L such that, for each i, s is within Hamming distance d from home substring, of length L, of si.