Getting all NNI trees of a parsimony tree

Question

I have an aligned protein sequence file which I have been using for reconstructing a parsimonious tree. I am currently using NNITreeSearcher._get_neighbors method from Biopython 1.72 but it's way to find one best scored tree only.

def _nni(self, starting_tree, alignment):
    """Search for the best parsimony tree using the NNI algorithm (PRIVATE)."""
    best_tree = starting_tree
    while True:
        best_score = self.scorer.get_score(best_tree, alignment)
        temp = best_score
        for t in self._get_neighbors(best_tree):
            score = self.scorer.get_score(t, alignment)
            if score < best_score:
                best_score = score
                best_tree = t
        # stop if no smaller score exist
        if best_score >= temp:
            break
    return best_tree

I need to generate all NNI-neighbours of the trees (two trees are NNI-neighbours if one can be transformed into another by one nearest neighbour interchange operation).

I want to know how can I get total number of trees generated before the best tree is reached.
Is it possible to return all the trees generated before the best tree is reached, so that the all/required number of trees(other than the best tree) may be printed?

score 4 · Answer 1 · answered Sep 11 '18 at 05:41

As I've studies the 'TreeConstruction' module of Biopython, I came to know that '_get_neighbors' method is the one that is used to get all neighbor trees of the given tree. This is all I've concluded from my findings. If anyone wants to add more, that'll be positively appreciated.

Getting all NNI trees of a parsimony tree

1 Answers1