On the relative efficiency of maximal clique enumeration algorithms, with application to high-throughput computational biology
The efficient enumeration of maximal cliques has applications in microarray analysis and a number of other foundational problems of computational biology. In this paper, we analyze and test existing maximal clique enumeration algorithms for various classes of graphs. The classic branch and bound alg...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | conferenceObject |
| Published: |
2005
|
| Online Access: | http://hdl.handle.net/10725/7500 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.4353&rep=rep1&type=pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | The efficient enumeration of maximal cliques has applications in microarray analysis and a number of other foundational problems of computational biology. In this paper, we analyze and test existing maximal clique enumeration algorithms for various classes of graphs. The classic branch and bound algorithm of Bron and Kerbosch proves to be relatively fast for sparse graphs, but slows considerably as edge density increases. Attempts to improve this algorithm are discussed. Experimental results demonstrate the difficulty of making improvements, especially when analyzing the overlap between cliques. Novel strategies for maximal clique enumeration algorithms are also described and placed in the context of ongoing research. |
|---|