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 contributionpeer-review

1 Scopus citations

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
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages115-118
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
Country/TerritoryCanada
CityOttawa, ON
Period7/05/0610/05/06

Keywords

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

Fingerprint

Dive into the research topics of 'New constraints on generation of uniform random samples from evolutionary trees'. Together they form a unique fingerprint.

Cite this