Title: A parallel approach to multiple sequences alignment and phylogenetic tree node labelling

Authors: Jingjing Wang, Mengxia Zhu

Addresses: Department of Computer Science, Southern Illinois University, Carbondale, IL 62901, USA. ' Department of Computer Science, Southern Illinois University, Carbondale, IL 62901, USA

Abstract: An evolutionary tree represents the relationship among a group of species or sequences. The quality of tree topology relies heavily on an efficient Multiple Sequence Alignment (MSA). Efficient and parallel algorithms are designed to utilise the computing power and memory in a supercomputer. A divide and conquer based parallel algorithm is implemented to perform optimal three sequence alignment with much reduced memory cost. All internal nodes generated from a parallel Maximum Likelihood tree software are labelled using our level order based parallel approach. Such node labelling process is also parallelised to lead to a two-level nested parallel computing strategy.

Keywords: maximum likelihood; MSA; multiple sequence alignment; phylogenetic trees; parallel computing; node labelling; tree topology.

DOI: 10.1504/IJCBDD.2010.038027

International Journal of Computational Biology and Drug Design, 2010 Vol.3 No.3, pp.226 - 236

Published online: 11 Jan 2011 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article