LIVIVO - The Search Portal for Life Sciences

zur deutschen Oberfläche wechseln
Advanced search

Search results

Result 1 - 3 of total 3

Search options

  1. Article ; Online: An exact algorithm to find a maximum weight clique in a weighted undirected graph.

    Rozman, Kati / Ghysels, An / Janežič, Dušanka / Konc, Janez

    Scientific reports

    2024  Volume 14, Issue 1, Page(s) 9118

    Abstract: We introduce a new algorithm MaxCliqueWeight for identifying a maximum weight clique in a weighted graph, and its variant MaxCliqueDynWeight with dynamically varying bounds. This algorithm uses an efficient branch-and-bound approach with a new weighted ... ...

    Abstract We introduce a new algorithm MaxCliqueWeight for identifying a maximum weight clique in a weighted graph, and its variant MaxCliqueDynWeight with dynamically varying bounds. This algorithm uses an efficient branch-and-bound approach with a new weighted graph coloring algorithm that efficiently determines upper weight bounds for a maximum weighted clique in a graph. We evaluate our algorithm on random weighted graphs with node counts up to 10,000 and on standard DIMACS benchmark graphs used in a variety of research areas. Our findings reveal a remarkable improvement in computational speed when compared to existing algorithms, particularly evident in the case of high-density random graphs and DIMACS graphs, where our newly developed algorithm outperforms existing alternatives by several orders of magnitude. The newly developed algorithm and its variant are freely available to the broader research community at http://insilab.org/maxcliqueweight , paving the way for transformative applications in various research areas, including drug discovery.
    Language English
    Publishing date 2024-04-20
    Publishing country England
    Document type Journal Article
    ZDB-ID 2615211-3
    ISSN 2045-2322 ; 2045-2322
    ISSN (online) 2045-2322
    ISSN 2045-2322
    DOI 10.1038/s41598-024-59689-x
    Database MEDical Literature Analysis and Retrieval System OnLINE

    More links

    Kategorien

    Order via subito

    This service is chargeable due to the Delivery terms set by subito. Orders including an article and supplementary material will be classified as separate orders. In these cases, fees will be demanded for each order.

  2. Article ; Online: Exact parallel maximum clique algorithm for general and protein graphs.

    Depolli, Matjaž / Konc, Janez / Rozman, Kati / Trobec, Roman / Janežič, Dušanka

    Journal of chemical information and modeling

    2013  Volume 53, Issue 9, Page(s) 2217–2228

    Abstract: A new exact parallel maximum clique algorithm MaxCliquePara, which finds the maximum clique (the fully connected subgraph) in undirected general and protein graphs, is presented. First, a new branch and bound algorithm for finding a maximum clique on a ... ...

    Abstract A new exact parallel maximum clique algorithm MaxCliquePara, which finds the maximum clique (the fully connected subgraph) in undirected general and protein graphs, is presented. First, a new branch and bound algorithm for finding a maximum clique on a single computer core, which builds on ideas presented in two published state of the art sequential algorithms is implemented. The new sequential MaxCliqueSeq algorithm is faster than the reference algorithms on both DIMACS benchmark graphs as well as on protein-derived product graphs used for protein structural comparisons. Next, the MaxCliqueSeq algorithm is parallelized by splitting the branch-and-bound search tree to multiple cores, resulting in MaxCliquePara algorithm. The ability to exploit all cores efficiently makes the new parallel MaxCliquePara algorithm markedly superior to other tested algorithms. On a 12-core computer, the parallelization provides up to 2 orders of magnitude faster execution on the large DIMACS benchmark graphs and up to an order of magnitude faster execution on protein product graphs. The algorithms are freely accessible on http://commsys.ijs.si/~matjaz/maxclique.
    MeSH term(s) Algorithms ; Computational Biology/methods ; Computer Graphics ; Models, Molecular ; Protein Conformation ; Proteins/chemistry ; Time Factors
    Chemical Substances Proteins
    Language English
    Publishing date 2013-09-23
    Publishing country United States
    Document type Journal Article ; Research Support, Non-U.S. Gov't
    ZDB-ID 190019-5
    ISSN 1549-960X ; 0095-2338
    ISSN (online) 1549-960X
    ISSN 0095-2338
    DOI 10.1021/ci4002525
    Database MEDical Literature Analysis and Retrieval System OnLINE

    More links

    Kategorien

    In stock of ZB MED Cologne/Königswinter

    Zs.A 1230: Show issues Location:
    Je nach Verfügbarkeit (siehe Angabe bei Bestand)
    bis Jg. 1994: Bestellungen von Artikeln über das Online-Bestellformular
    Jg. 1995 - 2021: Lesesall (1.OG)
    ab Jg. 2022: Lesesaal (EG)

    Order via subito

    This service is chargeable due to the Delivery terms set by subito. Orders including an article and supplementary material will be classified as separate orders. In these cases, fees will be demanded for each order.

  3. Article ; Online: Parallel-ProBiS: fast parallel algorithm for local structural comparison of protein structures and binding sites.

    Konc, Janez / Depolli, Matjaž / Trobec, Roman / Rozman, Kati / Janežič, Dušanka

    Journal of computational chemistry

    2012  Volume 33, Issue 27, Page(s) 2199–2203

    Abstract: The ProBiS algorithm performs a local structural comparison of the query protein surface against the nonredundant database of protein structures. It finds proteins that have binding sites in common with the query protein. Here, we present a new ... ...

    Abstract The ProBiS algorithm performs a local structural comparison of the query protein surface against the nonredundant database of protein structures. It finds proteins that have binding sites in common with the query protein. Here, we present a new parallelized algorithm, Parallel-ProBiS, for detecting similar binding sites on clusters of computers. The obtained speedups of the parallel ProBiS scale almost ideally with the number of computing cores up to about 64 computing cores. Scaling is better for larger than for smaller query proteins. For a protein with almost 600 amino acids, the maximum speedup of 180 was achieved on two interconnected clusters with 248 computing cores. Source code of Parallel-ProBiS is available for download free for academic users at http://probis.cmm.ki.si/download.
    MeSH term(s) Algorithms ; Binding Sites ; Computational Biology ; Databases, Protein ; Protein Conformation ; Proteins/chemistry
    Chemical Substances Proteins
    Language English
    Publishing date 2012-10-15
    Publishing country United States
    Document type Comparative Study ; Journal Article ; Research Support, Non-U.S. Gov't
    ZDB-ID 1479181-x
    ISSN 1096-987X ; 0192-8651
    ISSN (online) 1096-987X
    ISSN 0192-8651
    DOI 10.1002/jcc.23048
    Database MEDical Literature Analysis and Retrieval System OnLINE

    Full text online

    More links

    Kategorien

    Order via subito

    This service is chargeable due to the Delivery terms set by subito. Orders including an article and supplementary material will be classified as separate orders. In these cases, fees will be demanded for each order.

To top