Date of Award
12-1-2010
Degree Name
Master of Science
Department
Computer Science
First Advisor
Zhu, Mengxia
Abstract
An evolutionary tree represents the relationship among a group of species, DNA or protein sequences, and play fundamental roles in biological lineage research. A high quality tree construction relies heavily on optimal multiple sequence alignment (MSA), which aligns three or more sequence simultaneously to derive the similarity. On the other hand, a good tree can also be used to guide the MSA process. Due to the high computational cost to conduct both the MSA and tree construction, parallel approaches are exploited to utilize the enormous amount of computing power and memory housed in a supercomputer or Linux cluster. In this paper, first of all, a divide and conquer based parallel algorithm is designed and implemented to perform optimal three sequence alignment using reduced memory cost. Secondly, all internal nodes of a phylogenetic tree resulting from a parallel Maximum-likelihood inference software are labeled using the parallel MSA. Such tree node labeling process is carried out from top down and is also parallelized to fully utilize the numerous cores and nodes in a high performance computing facility.
Access
This thesis is only available for download to the SIUC community. Current SIUC affiliates may also access this paper off campus by searching Dissertations & Theses @ Southern Illinois University Carbondale from ProQuest. Others should contact the interlibrary loan department of your local library or contact ProQuest's Dissertation Express service.