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

[Peter Cock]

On Sat, Oct 19, 2013 at 4:16 PM, Jing Lu <ajingnk at gmail.com> wrote:
> 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.

Does it have to be in pure Python?

Whenever I've needed a large tree with 1000s of sequences
I have used a fast C implementation, with bootstrapping.

Peter