Abstract

Current progress in genome research projects has generated huge amount of data. As a result, the analysis of these data is now a bottleneck in bioinformatics. Multiple sequence alignment is an important step in this kind of analysis. It compares unknown sequences with well studied ones, and thus infers functional and structural information of the unknown sequences. However, due to the NP-completeness nature of the multiple sequence alignment, exhaustive searching method is unrealistic. Current algorithms use heuristic approach to get a nearly global optimal result. As a consequence, any specific program may encounter certain cases that it is not good at. In this work, we use protein motif databases to improve the alignment. The basic idea is to detect possible occurrences of motifs on the sequences, and force those parts to be aligned together. Unlike existing programs, this method uses biological information instead of treating it as purely an optimization problem. It also reduces the searching space. Experiments show that using motif databases could generate good results