Walks on SPR Neighborhoods

Details Walks on SPR Neighborhoods Walks on SPR Neighborhoods

2011-10-05

arxiv.org/abs/1110.1114v1

Biology

Quantitative Biology

Populations and Evolution

Scientific paper

A nearest-neighbor-interchange (NNI) walk is a sequence of unrooted phylogenetic trees, T_0, T_1, T_2,... where each consecutive pair of trees differ by a single NNI move. We give tight bounds on the length of the shortest NNI-walks that visit all trees in an subtree-prune-and-regraft (SPR) neighborhood of a given tree. For any unrooted, binary tree, T, on n leaves, the shortest walk takes {\theta}(n^2) additional steps than the number of trees in the SPR neighborhood. This answers Bryant's Second Combinatorial Conjecture from the Phylogenetics Challenges List, the Isaac Newton Institute, 2011, and the Penny Ante Problem List, 2009.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-180579