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 Citations (Scopus)

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
StatePublished - 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

Maximum likelihood

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
Bhattacharjee, Anupam ; Sultana, Kazi Zakia ; Shams, Zalia. / Dynamic and parallel approaches to optimal evolutionary tree construction. 2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06. Institute of Electrical and Electronics Engineers Inc., 2006. pp. 119-122 (Canadian Conference on Electrical and Computer Engineering).
@inproceedings{027bf43d4fc84fe8aa0880658def5838,
title = "Dynamic and parallel approaches to optimal evolutionary tree construction",
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.",
keywords = "Bioinformatics, Evolutionary tree construction, Parallel algorithm, Shared memory model",
author = "Anupam Bhattacharjee and Sultana, {Kazi Zakia} and Zalia Shams",
year = "2006",
month = "1",
day = "1",
doi = "10.1109/CCECE.2006.277582",
language = "English",
isbn = "1424400384",
series = "Canadian Conference on Electrical and Computer Engineering",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "119--122",
booktitle = "2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06",

}

Bhattacharjee, A, Sultana, KZ & Shams, Z 2006, Dynamic and parallel approaches to optimal evolutionary tree construction. in 2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06., 4054620, Canadian Conference on Electrical and Computer Engineering, Institute of Electrical and Electronics Engineers Inc., pp. 119-122, 2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06, Ottawa, ON, Canada, 7/05/06. https://doi.org/10.1109/CCECE.2006.277582

Dynamic and parallel approaches to optimal evolutionary tree construction. / Bhattacharjee, Anupam; Sultana, Kazi Zakia; Shams, Zalia.

2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06. Institute of Electrical and Electronics Engineers Inc., 2006. p. 119-122 4054620 (Canadian Conference on Electrical and Computer Engineering).

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

TY - GEN

T1 - Dynamic and parallel approaches to optimal evolutionary tree construction

AU - Bhattacharjee, Anupam

AU - Sultana, Kazi Zakia

AU - Shams, Zalia

PY - 2006/1/1

Y1 - 2006/1/1

N2 - 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.

AB - 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.

KW - Bioinformatics

KW - Evolutionary tree construction

KW - Parallel algorithm

KW - Shared memory model

UR - http://www.scopus.com/inward/record.url?scp=39049117347&partnerID=8YFLogxK

U2 - 10.1109/CCECE.2006.277582

DO - 10.1109/CCECE.2006.277582

M3 - Conference contribution

AN - SCOPUS:39049117347

SN - 1424400384

SN - 9781424400386

T3 - Canadian Conference on Electrical and Computer Engineering

SP - 119

EP - 122

BT - 2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

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