The Parallel And Heuristic Algorithms For Sequence Alignment In Bioinformatics

The main task of bioinformatics is to study the structure and evolutionary information of DNA or proteins sequences using mathematical theory, computer technology and its network. Sequence Alignment is by far the most important and fundamental tool in molecular biology and bioinformatics. It plays an essential role in sequence analysis, reconstruction of phylogenetic trees, detecting regions of significant sequence similarity in collections of primary sequences, and predicting the secondary and tertiary structure. Significant information of sequence similarity, functional domains, structures, and evolutionary process can be detected by means of sequence alignment.In this paper, we present a fast and scalable parallel algorithm for two sequence alignment on the parallel computational model LARPBS which is based on reconfigurable optical bus. In addition, we also advance three different algorithms for multiple sequence alignment problem based on ant colony algorithm. Furthermore, we give the prospect of our further research work in this area.The sequence alignment problem is of high complexity because of the huge biological information. We present a fast and efficient sequence alignment algorithm on LARPBS. For two sequences with lengths of m, n respectively, the algorithm can be implemented in O(mn/p) time with p processors(1≤p≤max{m,n}). Since the time complexity of the algorithm can be adjusted by choosing different numbers of processors p, the algorithm is highly scalable. Furthermore, it is the fastest and cost-optimal parallel algorithm for the sequence alignment problem.Since the lengths of biosequences are usually large, biosequences alignment has very high computational complexity, especially for multisequences alignment. It has been proved that multiple sequence alignment is a NP-hard problem even though the scoring function is very simple. It is not practical to obtain the accurate multiple alignment of biological sequences due to the huge computational cost. Therefore, many...