الفهرس 
Chapter 1 IntroductionOnly 14 pages are availabe for public view
 |  | from | 148 |  |  |
| | | from | 148 | | |
Abstract
Multiple sequence alignment is one problem of bioinformatics. Many techniques discussed with the aim of solving this problem. This thesis proposes a Multiple Sequence Alignment (MSA) algorithm Position-based Multiple Sequence Alignment (PoMSA). This thesis support the proposed algorithm by providing a partitioning schema so that each partition can separately processed by the algorithm and satisfies higher matching score.
This thesis studies the state-of-the-art parallel MSA algorithms from two different perspectives, performance and accuracy. Four different multiple sequence algorithms like T-Coffee, MAFFT, MSAProbs, and M2Align are selected and a detailed explanation of each algorithm and the available parallel implementation on multicore systems have been discussed. Because of the bad of accuracy and execution time some algorithms have, the Parallel POMSA provide solution to finish this task. The results show that the execution time will decreased up to 50% compared to other algorithms and sequential version and also SP score will be increased in the case of increasing number of partitions. The accuracy evaluated by computing the TC and Q score for POMSA and other algorithms MAFFT, Clustal-Omega and MUSCLE, the result shows that POMSA achieved high accuracy when compared to these algorithms.
We proposed a parallel version of PoMSA that run on GPUs that improve the execution time. An extended algorithm of M2Align algorithm that is B-M2Align (Bitmap M2Align) is introduced that use the bit map index strategy with the goal of improving the performance and minimize the execution time and memory location used. The results show that when using bitmap indexing strategy in coding scheme it can minimize the time and location used to half when compared to traditional M2Align with its encoding scheme.