I have a distance matrix with more than 1M nodes. I wonder whether there exist any Neighbour Joining implementation which could calculate a tree structure within a reasonable amount of time. The complexity for Neighbour Joining is N^3, so I am not sure whether there is any heuristic algorithm could do this.
Currently, I have a distance matrix. If there is another comparable tree building algorithm starting from distance matrix, I would like to try that method also.
1 answer
It is pushing the limits but likely possible. Although the worst-case performance of Neighbour Joining is N^3, there are heuristics that evolve N^2 on most actual data. I would take a look at RapidNJ and related work by the same group. NINJA might be a viable option too. Extrapolating based on N^2 scaling and a runtime of 100 seconds for 8000 taxa, you are looking at runtime in the order of a few weeks.
•
written
by
Lars Juhl Jensen
I am not sure. I think eRapidNJ (the paper I linked to) is where it was introduced, but I have not found the code. If RapidNJ takes too much memory, I would suggest you contact the authors of the eRapidNJ article.
The authors state that *first* they reduce the memory requirement by a factor of two by storing only the lower triangular matrix. On the next page they explain how they further reduce the memory consumption by not storing only some columns in memory at a time.
You may be right. However, one thing really mystifies me: in the abstract the authors state that the N^2 memory consumption becomes a problem for large trees, and that the new algorithm is applicable to very large trees. That does not make much sense if the new algorithm also requires N^2 memory, does it?
Log in to answer this question.
-
Advice on building custom sequence aligning tool for educational reasons
written by dalelmccauley •
-
sequence distance to consensus shorter than within NJ tree?
written by tenax •
-
goal of neighbour joining algorithm
written by mi.aghajohari •
-
Drawing phylogenetic tree in line format and Newick format from branch lengths
written by listerr01 •
-
The coverage of a set of protein sequences to all possible human protein
written by ajingnk
-
How To Plot An Unrooted Tree With Flexible Changes Of Leaf Node Size?
written by ajingnk
-
Is There Software For Phylogenetic Placement Of Short Sequence Reads That Does Not Require Knowledg…
written by samlambrechts299
-
How To Prevent Neighbour-Joining Resulted Negative Branch Length For Phylogenetic Tree Drawing?
written by Ken •
-
How Should I Go To Align Protein Sequences Having Different Lengths?Any Algorithms/Software ?
written by Sagar Nikam
-
Phylip Distance Matrix Question
written by Deena •
1M*1M=1TB. If you have a matrix in float, that is 4TB. An algorithm are likely to keep a few such matrices. Do you have a machine with ~10TB RAM? If your main purpose is clustering, there are more appropriate algorithms than NJ.
There are in fact efficient algorithms that do not require having the entire matrix loaded into memory.
I haven't seen a popular implementation of hierarchical clustering with complexity less than N^2
What will you do next after you get the tree? If you are to cluster nodes into groups, you can do clustering directly without a tree. There are many clustering algorithms. Hierarchical clustering is just a very basic one.
I need the tree structure for visualization.
Suppose you managed to do the clustering. How do you imagine showing the hierarchical structure of a tree with 1M leaf nodes? It sounds to me like your actual problem is much more about big-data visualization than it is about the computational challenge.
A tree with 1M leaf nodes is about 2M nodes and 2M edges. I was thinking to use Gephi.. But, I guess I should reduce the size of the data first.
If the starting point is an all-against-all similarity matrix, it is theoretically impossible to do better than N^2, since just reading through the similarity matrix is N^2.
Yes, you are right. N^2 is the best the algorithm can do.