Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data

Details Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data

2012-03-15

arxiv.org/abs/1203.3284v1

Computer Science

Data Structures and Algorithms

Extended abstract to appear in 11th International Symposium on Experimental Algorithms (SEA 2012)

Scientific paper

We study a character-based phylogeny reconstruction problem when an incomplete set of data is given. More specifically, we consider the situation under the directed perfect phylogeny assumption with binary characters in which for some species the states of some characters are missing. Our main object is to give an efficient algorithm to enumerate (or list) all perfect phylogenies that can be obtained when the missing entries are completed. While a simple branch-and-bound algorithm (B&B) shows a theoretically good performance, we propose another approach based on a zero-suppressed binary decision diagram (ZDD). Experimental results on randomly generated data exhibit that the ZDD approach outperforms B&B. We also prove that counting the number of phylogenetic trees consistent with a given data is #P-complete, thus providing an evidence that an efficient random sampling seems hard.

Affiliated with

Also associated with

No associations

Rating

Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-30401