Sequence alignment : algorithm development and applications

Sequence alignment is a critical step towards sequence comparison and it can reveal genetic/functional relationships among evolutionarily related species. The alignment addresses similarities among sequences by placing them together in rows and put identical or similar characters in the same column. While the problem description is straightforward enough, the alignment of multiple sequences is proved to be NP hard. Different methods have been proposed to accomplish this task. Most of them are based on progressive extensions of pairwise alignment methods. The limitation of these methods is that the final alignment result heavily depends on the order of pairwise alignment, while there is no consensus about the proper ordering of pairwise alignment. In this thesis, a layer-based method is proposed to simultaneously align multiple DNA/RNA sequences. Sequence delamination and Gaussian scale space filter are used to separate sequences into letter layers and to dig out underlying pattern sequence. Final alignment is given by aligning single sequences onto the pattern sequence. The layer-based method bypasses the ordering problem in traditional progressive approaches and achieves a comparable accuracy. The importance of sequence alignment is highly appreciated by biologists. And the direct application of alignment on biological question is desired. An alignment based method is proposed to solve the phosphorylation sequence prediction problem. By applying pairwise sequence alignment, the method uses one experiment verified phosphorylatable sequence as seed to predict phosphorylatable sequences from a given database. Experiment shows it achieves satisfying accuracy