I produced a phylo-tree with Mafft that contains 30000 nodes. I would like to cluster the nodes to find relevant groups among my genes. I do not have the alignment since Mafft is not able to produce such a big alignment with sequences with low homology.
I have tried to use software for clustering like Phylopart or Clustermaker within Cytoscape, but everything crashes because of the memory handling problems.
Any advice regarding what software to use and how to proceed. I would appreciate any direct help since I am in a hurry to present results.
@Paco have you been discussing the issue at hand with the people behind development of the goeBurst approach from Lisbon (João André Carriço et al.)? Given the territorial proximity it should be my fist step :) .
Esp. as perhaps just recomplilation of that code would suffice to run the problem of this size on a sufficiently large machine?
I don't have a direct answer. However, having a tree means the data have been effectively clustered already to produce the tree. I wonder what is the downside to simply cutting the tree into a certain number of subtrees, as opposed to whatever kind of clustering Francisco is trying to do. Or is it simply a question of where to cut to get clusters with special qualities? What qualities would these normaly be?
@Matej - exactly: "where to cut?" and also how to identify such to be cut at nodes is sort of NP-hard problem - relatively easy to perform visually, but a bit tough to cast it into an efficient algorithm
Thanks Jan.... no idea that João was dealing with that... In fact I am just a floor above him ... I will talk about that.
@Matej... I agree with you. The tree is already constructed, so we have some degree of clustering, but I would like to have something that give me out this information producing groups of closely related genes as the Cytoscape plugin ClusterMAKER does.
@Paco, I'd be truly curious whether [possibly recomplied for a huge size] goeBurst can handle this kind of problems at all / efficiently :) ?
@Jan: Thanks for the reply. I am sorry, but I can't see where the NP-hard part is coming from. Building the tree, yes, could be. But analyzing it (once it's built)? Could it be NP-hard? The topology of the tree is already fixed, I suppose. If the tree is rooted, I can just go from the root to the branches, cut every edge on my way until that operation creats two clusters violating some required property of the cluster. At that point I step back and perform this on other branches. Unless the property is really weird, this should be P. Even if it is not rooted, there is at most n possible roots... Please, correct me, if I am wrong here.
Sorry, I wasn't clear enough - for the problem of this size, the question of to what extend any given tree is closer to the underlying reality if a fundamental importance IMO, esp. due to a problem of branches entanglement, so the pairs of ancestor & descendant found on the tree might in fact be a very, very distant cousins = many edges distant.
@Jan... no idea about the recompiling.... João is missing... I have to ask him, but I am not sure if his software is useful for that...
@Paco - a related question, this time to you: what there is known about the quality of trees produced by MAFFT?
So far I was always using MUSCLE for my multiple alignment problems, but admittedly never on such a scale - the largest was perhaps about 10k nodes.
@Jan... I was in contact with the people in Osaka University who developed Mafft. In fact in order to construct an alignment the softwae need to have quite similar sequences. In my case, and because sequences are not so similar, is difficult to build up.
Can MUSCLE handle more than 30k nodes?.
@Paco, this I really don't know - there was a paper describing a parallel implementation several years back http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1639616 , so perhaps it can be compiled on one of bigger machines here, with an appropriate memory resources, but would need to check with our supercomputer admins for a practical feasibility
- Badges
- Science topic
- Similar topics
- Bioinformatics
- Bioinformatics and Computational Biology