Tree Contractions and Evolutionary Trees

Details Tree Contractions and Evolutionary Trees Tree Contractions and Evolutionary Trees

2001-01-26

arxiv.org/abs/cs/0101030v1

SIAM Journal on Computing, 27(6):1592--1616, December 1998

Computer Science

Computational Engineering, Finance, and Science

Scientific paper

An evolutionary tree is a rooted tree where each internal vertex has at least two children and where the leaves are labeled with distinct symbols representing species. Evolutionary trees are useful for modeling the evolutionary history of species. An agreement subtree of two evolutionary trees is an evolutionary tree which is also a topological subtree of the two given trees. We give an algorithm to determine the largest possible number of leaves in any agreement subtree of two trees T_1 and T_2 with n leaves each. If the maximum degree d of these trees is bounded by a constant, the time complexity is O(n log^2(n)) and is within a log(n) factor of optimal. For general d, this algorithm runs in O(n d^2 log(d) log^2(n)) time or alternatively in O(n d sqrt(d) log^3(n)) time.

Affiliated with

Also associated with

No associations

Rating

Tree Contractions and Evolutionary Trees 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 Tree Contractions and Evolutionary Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tree Contractions and Evolutionary Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-278179