Dynamic and parallel approaches to optimal evolutionary tree construction

Anupam Bhattacharjee, Kazi Zakia Sultana, Zalia Shams

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Phylogenetic trees are commonly reconstructed based on hard optimization problems such as Maximum parsimony (MP) and Maximum likelihood (ML). Conventional MP heuristics for producing phylogenetic trees produce good solutions within reasonable time on small databases (up to a few thousand sequences) while ML heuristics are limited to smaller datasets (up to a few hundred sequences). However, since MP and ML are NP-hard, application of such approaches do not scale large datasets. In this paper, we present a promising divide-and-conquer technique, the TAZ method, to construct an evolutionary tree. The algorithm has been implemented and tested against five large biological datasets ranging from 5000-7000 sequences and dramatic speedup with significant improvement in accuracy (better than 94%), in comparison to existing approaches, has been obtained. Thus, high quality reconstruction can be obtained for large datasets by using this approach. Moreover, we present here another approach to construct the tree dynamically (when sequences come dynamically with partial information). Finally Combining the two approaches, we show parallel approaches to construct the tree when sequences are generated or obtained dynamically.

Original languageEnglish
Title of host publication2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages119-122
Number of pages4
ISBN (Print)1424400384, 9781424400386
DOIs
Publication statusPublished - 1 Jan 2006
Event2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06 - Ottawa, ON, Canada
Duration: 7 May 200610 May 2006

Publication series

NameCanadian Conference on Electrical and Computer Engineering
ISSN (Print)0840-7789

Conference

Conference2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06
CountryCanada
CityOttawa, ON
Period7/05/0610/05/06

    Fingerprint

Keywords

  • Bioinformatics
  • Evolutionary tree construction
  • Parallel algorithm
  • Shared memory model

Cite this

Bhattacharjee, A., Sultana, K. Z., & Shams, Z. (2006). Dynamic and parallel approaches to optimal evolutionary tree construction. In 2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06 (pp. 119-122). [4054620] (Canadian Conference on Electrical and Computer Engineering). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CCECE.2006.277582