search

McGill-CSB / PHYLO

a gaming framework to align genomic data
phylo.cs.mcgill.ca/edge
Other
11 stars 14 forks source link

Question: Have advances in MSA algorithms/implementations made PHYLO obselete? #114

Closed movermeyer closed 6 years ago

movermeyer commented 6 years ago

It's been a few years since the development of PHYLO.

Since then, there have been advances in MSA.

Do things like QuickProbs, or D-Wave's qbsolv (or something else) mean that computers are now able to find better solutions than those found on the PHYLO beginner (non-expert mode) problems?

waldispuhl commented 6 years ago

The problem is still open. The computational efficiency has indeed been improved for very large MSAs but it targets MSAs with a size that goes far beyond what humans can do (as far as I can see in these papers). The initial purpose of Phylo is to provide a refined exploration of regions of the MSAs where thes algorithms fail to find a good solution (i.e. the alignment maybe globally good but some regions could be improved). We're also exploring different opportunities (i.e. learning better algo from the data collected). Overall, computational advances can be used to improve the current pipeline. Nonetheless, a refreshed benchmark would probably be a good idea.

movermeyer commented 6 years ago

Thanks! Very informative.

I didn't realize that the puzzles were the portions where existing algorithms had trouble getting a good solution.

I suppose the solution space is so large that even advances in hardware and parallel processing will never allow for a brute force solution (if I'm counting right, the first Digestive and Respiratory puzzle has ~2^148 possible positions!).