[Biopython] More efficient neighbor joining algorithm to build phylogenetic tree

Jing Lu ajingnk at gmail.com
Sat Oct 19 15:16:21 UTC 2013


Hello!

I am trying to build a large tree (~10000 nodes) from a distance matrix by
neighbor joining algorithm. I just modify the existing code from:
https://github.com/lijax/biopython/blob/master/Bio/Phylo/TreeConstruction.py
.

I thought this might be part of biopython in the future. However, the speed
for function nj() (neigbhor joining) is slow. The computational complexity
of this function is N**3, and the function takes about 1 day to build a
tree with 1000 nodes.

I am wondering whether there is any efficient algorithm for neighbor
joining in biopython or python. Probably, I can write a function based on
"fastphylo: Fast tools for phylogenetics" for biopython.


Thanks,
Jing



More information about the Biopython mailing list