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!
|
| _version_ | 1864513482380017664 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Baldwin, Nicole E. Langston, Micheal A. Samatova, Nagiza F. |
| author2_role | author author author |
| author_facet | Abu-Khzam, Faisal N. Baldwin, Nicole E. Langston, Micheal A. Samatova, Nagiza F. |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Baldwin, Nicole E. Langston, Micheal A. Samatova, Nagiza F. |
| dc.date.none.fl_str_mv | 2005 2018-04-24T09:55:39Z 2018-04-24T09:55:39Z 2018-04-24 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/7500 Abu-Khzam, F. N., Baldwin, N. E., Langston, M. A., & Samatova, N. F. (2005). On the relative efficiency of maximal clique enumeration algorithms, with applications to high-throughput computational biology. In International Conference on Research Trends in Science and Technology. 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 |
| dc.language.none.fl_str_mv | en |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | On the relative efficiency of maximal clique enumeration algorithms, with application to high-throughput computational biology |
| dc.type.none.fl_str_mv | Conference Paper / Proceeding info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/conferenceObject |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | conferenceObject |
| id | LAURepo_e2a4afdd413289d5aac92e36e8635def |
| identifier_str_mv | Abu-Khzam, F. N., Baldwin, N. E., Langston, M. A., & Samatova, N. F. (2005). On the relative efficiency of maximal clique enumeration algorithms, with applications to high-throughput computational biology. In International Conference on Research Trends in Science and Technology. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/7500 |
| publishDate | 2005 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | On the relative efficiency of maximal clique enumeration algorithms, with application to high-throughput computational biologyAbu-Khzam, Faisal N.Baldwin, Nicole E.Langston, Micheal A.Samatova, Nagiza F.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.N/A2018-04-24T09:55:39Z2018-04-24T09:55:39Z20052018-04-24Conference Paper / Proceedinginfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/conferenceObjecthttp://hdl.handle.net/10725/7500Abu-Khzam, F. N., Baldwin, N. E., Langston, M. A., & Samatova, N. F. (2005). On the relative efficiency of maximal clique enumeration algorithms, with applications to high-throughput computational biology. In International Conference on Research Trends in Science and Technology.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttp://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.4353&rep=rep1&type=pdfeninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/75002021-03-19T10:43:12Z |
| spellingShingle | On the relative efficiency of maximal clique enumeration algorithms, with application to high-throughput computational biology Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | On the relative efficiency of maximal clique enumeration algorithms, with application to high-throughput computational biology |
| title_full | On the relative efficiency of maximal clique enumeration algorithms, with application to high-throughput computational biology |
| title_fullStr | On the relative efficiency of maximal clique enumeration algorithms, with application to high-throughput computational biology |
| title_full_unstemmed | On the relative efficiency of maximal clique enumeration algorithms, with application to high-throughput computational biology |
| title_short | On the relative efficiency of maximal clique enumeration algorithms, with application to high-throughput computational biology |
| title_sort | On the relative efficiency of maximal clique enumeration algorithms, with application to high-throughput computational biology |
| url | 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 |