New constraints on generation of uniform random samples from evolutionary trees

Anupam Bhattacharjee, Zalia Shams, Kazi Zakia Sultana

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

In this paper, we introduce new algorithms for selecting taxon samples from large evolutionary trees, maintaining uniformity and randomness, under certain new constraints on the taxa. The algorithms are efficient as their runtimes and space complexities are polynomial. The algorithms have direct applications to the evolution of phylogenetic tree and efficient supertree construction using biologically curated data. We also present new lower bounds for the problem of constructing evolutionary tree from experiment under some earlier stated constraints. All the algorithms have been implemented.

Original languageEnglish
Title of host publication2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06
Pages115-118
Number of pages4
DOIs
StatePublished - 1 Dec 2007
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

Polynomials
Experiments

Keywords

  • Bioinformatics
  • Evolutionary tree
  • NP-hardproblems
  • Polynomial algorithms
  • Randomness
  • Uniformity

Cite this

Bhattacharjee, A., Shams, Z., & Sultana, K. Z. (2007). New constraints on generation of uniform random samples from evolutionary trees. In 2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06 (pp. 115-118). [4054619] (Canadian Conference on Electrical and Computer Engineering). https://doi.org/10.1109/CCECE.2006.277581
Bhattacharjee, Anupam ; Shams, Zalia ; Sultana, Kazi Zakia. / New constraints on generation of uniform random samples from evolutionary trees. 2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06. 2007. pp. 115-118 (Canadian Conference on Electrical and Computer Engineering).
@inproceedings{8770954f70dc449293af413754fd7daa,
title = "New constraints on generation of uniform random samples from evolutionary trees",
abstract = "In this paper, we introduce new algorithms for selecting taxon samples from large evolutionary trees, maintaining uniformity and randomness, under certain new constraints on the taxa. The algorithms are efficient as their runtimes and space complexities are polynomial. The algorithms have direct applications to the evolution of phylogenetic tree and efficient supertree construction using biologically curated data. We also present new lower bounds for the problem of constructing evolutionary tree from experiment under some earlier stated constraints. All the algorithms have been implemented.",
keywords = "Bioinformatics, Evolutionary tree, NP-hardproblems, Polynomial algorithms, Randomness, Uniformity",
author = "Anupam Bhattacharjee and Zalia Shams and Sultana, {Kazi Zakia}",
year = "2007",
month = "12",
day = "1",
doi = "10.1109/CCECE.2006.277581",
language = "English",
isbn = "1424400384",
series = "Canadian Conference on Electrical and Computer Engineering",
pages = "115--118",
booktitle = "2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06",

}

Bhattacharjee, A, Shams, Z & Sultana, KZ 2007, New constraints on generation of uniform random samples from evolutionary trees. in 2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06., 4054619, Canadian Conference on Electrical and Computer Engineering, pp. 115-118, 2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06, Ottawa, ON, Canada, 7/05/06. https://doi.org/10.1109/CCECE.2006.277581

New constraints on generation of uniform random samples from evolutionary trees. / Bhattacharjee, Anupam; Shams, Zalia; Sultana, Kazi Zakia.

2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06. 2007. p. 115-118 4054619 (Canadian Conference on Electrical and Computer Engineering).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

T1 - New constraints on generation of uniform random samples from evolutionary trees

AU - Bhattacharjee, Anupam

AU - Shams, Zalia

AU - Sultana, Kazi Zakia

PY - 2007/12/1

Y1 - 2007/12/1

N2 - In this paper, we introduce new algorithms for selecting taxon samples from large evolutionary trees, maintaining uniformity and randomness, under certain new constraints on the taxa. The algorithms are efficient as their runtimes and space complexities are polynomial. The algorithms have direct applications to the evolution of phylogenetic tree and efficient supertree construction using biologically curated data. We also present new lower bounds for the problem of constructing evolutionary tree from experiment under some earlier stated constraints. All the algorithms have been implemented.

AB - In this paper, we introduce new algorithms for selecting taxon samples from large evolutionary trees, maintaining uniformity and randomness, under certain new constraints on the taxa. The algorithms are efficient as their runtimes and space complexities are polynomial. The algorithms have direct applications to the evolution of phylogenetic tree and efficient supertree construction using biologically curated data. We also present new lower bounds for the problem of constructing evolutionary tree from experiment under some earlier stated constraints. All the algorithms have been implemented.

KW - Bioinformatics

KW - Evolutionary tree

KW - NP-hardproblems

KW - Polynomial algorithms

KW - Randomness

KW - Uniformity

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

U2 - 10.1109/CCECE.2006.277581

DO - 10.1109/CCECE.2006.277581

M3 - Conference contribution

SN - 1424400384

SN - 9781424400386

T3 - Canadian Conference on Electrical and Computer Engineering

SP - 115

EP - 118

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

ER -

Bhattacharjee A, Shams Z, Sultana KZ. New constraints on generation of uniform random samples from evolutionary trees. In 2006 Canadian Conference on Electrical and Computer Engineering, CCECE'06. 2007. p. 115-118. 4054619. (Canadian Conference on Electrical and Computer Engineering). https://doi.org/10.1109/CCECE.2006.277581