Try different enumeration techniques

cbg-ethz / haploclique

Viral quasispecies assembly via maximal clique finding. A method to reconstruct viral haplotypes and detect large insertions and deletions from NGS data.

GNU General Public License v3.0

25 stars 33 forks source link

Try different enumeration techniques #15

Open armintoepfer opened 7 years ago

armintoepfer commented 7 years ago

Try out heuristic MCE algos by Eppstein or enumerate quasi-cliques.

Potential drop in replacements:

https://github.com/darrenstrash/quick-cliques
http://c0de-x.com/how-to-find-maximal-cliques/

tobiasmarschall commented 7 years ago

What's a heuristic MCE algorithm? An algorithm that is allowed to miss some max cliques? Note that Bernhard implemented the Eppstein-Löffler-Strash algorithm that seems to be implemented in quick cliques. I would prioritize approaches to limit the number of enumerated (quasi)cliques over faster algorithms to enumerate all max cliques. Marcel's thesis might be worthwhile to read for examples where the current approach breaks.