Mirroring co-evolving trees in the light of their topologies

Details Mirroring co-evolving trees in the light of their topologies Mirroring co-evolving trees in the light of their topologies

2011-10-26

arxiv.org/abs/1110.5704v1

Biology

Quantitative Biology

Populations and Evolution

13 pages, 2 figures, Iman Hajirasouliha and Alexander Sch\"onhuth are joint first authors

Scientific paper

Determining the interaction partners among protein/domain families poses hard computational problems, in particular in the presence of paralogous proteins. Available approaches aim to identify interaction partners among protein/domain families through maximizing the similarity between trimmed versions of their phylogenetic trees. Since maximization of any natural similarity score is computationally difficult, many approaches employ heuristics to maximize the distance matrices corresponding to the tree topologies in question. In this paper we devise an efficient deterministic algorithm which directly maximizes the similarity between two leaf labeled trees with edge lengths, obtaining a score-optimal alignment of the two trees in question. Our algorithm is significantly faster than those methods based on distance matrix comparison: 1 minute on a single processor vs. 730 hours on a supercomputer. Furthermore we have advantages over the current state-of-the-art heuristic search approach in terms of precision as well as a recently suggested overall performance measure for mirrortree approaches, while incurring only acceptable losses in recall. A C implementation of the method demonstrated in this paper is available at http://compbio.cs.sfu.ca/mirrort.htm

Affiliated with

Also associated with

No associations

Rating

Mirroring co-evolving trees in the light of their topologies 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 Mirroring co-evolving trees in the light of their topologies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mirroring co-evolving trees in the light of their topologies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-716879