search

sriramlab / OrientAGraph

GNU General Public License v3.0
11 stars 1 forks source link

The program got stuck when "Performing exhaustive search to add migration edge to base tree" #7

Closed ZheCai closed 1 year ago

ZheCai commented 2 years ago

Hi,

I found the program often got stuck when migration edges more than 6. The output log has never refreshed for many days after printing "Performing exhaustive search to add migration edge to base tree". I'm sure the program is still running (%CPU is 100%), but no output anymore.

Is this a bug? Or it's a problem due to my data?

Thanks!

ekmolloy commented 2 years ago

Hello,

How many populations (leaf nodes) do you have? During the orientation step, we evaluate the likelihood of O(n choose 5) orientations, where n is the number of populations. If n is 50, this is 2,118,760 combinations. This could take a long time. However, it's also possible the program is stuck. I will add a message so that you can check.

Thanks! -Erin

ekmolloy commented 2 years ago

Note that you had -m 5 in your last message so I am assuming you still have 5. If you have 6, then this would O(n choose 6) which is 15,890,700 combinations for n - 50. In this case, it seems unlikely to complete. I recommend using -mlno 4, which will only perform orientation for the first 4 admixture edge additions. Thanks!

ZheCai commented 2 years ago

I have 7 pops for running (including one Outgroup pop). Only two runs (with m=7) have normal output in ten replicates.

Thanks for your suggestion, I will have a try with the -mlno option.

ekmolloy commented 2 years ago

OrientAGraph and methods based on the same approximate likelihood function (e.g., TreeMix) are unlikely to work with 7 populations and 7 migration edges. I recommend reading Mark Lipson's 2020 review (download here: https://onlinelibrary.wiley.com/doi/10.1111/1755-0998.13230) and then counting the number of knowns vs. unknowns. Another good check is to run the original TreeMix method and to see if it quits without adding all seven migration edges. I will look into adding an error message to OrientAGraph rather than it stalling out.

ZheCai commented 2 years ago

According to the paper, there doesn't seem to be enough constraints for 7 migration edges among 7 pops, and the most number of migration edges should be 5 for seven pops if I understand correctly.

Yes, I also run treemix using the same data, it doesn't quit even when 9 migration edges are added. (Although the parameters can not be estimated reliably in this case.)

Your suggestions are extremely informative. I'm most grateful for your help!

ekmolloy commented 2 years ago

Happy to help! :) This is a common challenge - so I will try to make it so that OrientAGraph throws an informative error message in this situation rather than getting stuck.

ZheCai commented 2 years ago

Thank you very much! The problem has been solved after adding the options -mlno 1,2,3,4 and -allmigs 1,2,3,4. The resulting tree topology also makes sense (This is why I adopted OrientAGraph, treemix usually generated weird trees in my data).