Finding transcription factor binding sites based on multiple pairwise alignment

The motif detection problem has been well studied and several algorithms have been developed in the past few years. Although some are better than the others in a sense, yet not a single one is recognized to be the best. However, since Pevzner and Sze defined a "challenge problem" in motif detection, most of the algorithms, which were considered to be good, have showed their inability to solve this problem. Then some new algorithms have been proposed to solve this "challenge problem", but the computation cost is a big problem all the same. In this paper, we present a new method based on multiple pairwise alignment to solve the "challenge problem" with less computation cost than the existing methods. This new method combines profile-driven method with pattern-driven method. So it has the advantages of both profile-driven method and pattern-driven method. It has high success rate in finding the motif and less computation cost. We refer to the new method as FMMPA (finding motif based on multiple pairwise alignment).