iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://pubmed.ncbi.nlm.nih.gov/26356014
Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage - PubMed Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2014 May-Jun;11(3):455-67.
doi: 10.1109/TCBB.2013.177.

Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage

Falk Hüffner, Christian Komusiewicz, Adrian Liebtrau, Rolf Niedermeier

Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage

Falk Hüffner et al. IEEE/ACM Trans Comput Biol Bioinform. 2014 May-Jun.

Abstract

A popular clustering algorithm for biological networks which was proposed by Hartuv and Shamir identifies nonoverlapping highly connected components. We extend the approach taken by this algorithm by introducing the combinatorial optimization problem Highly Connected Deletion, which asks for removing as few edges as possible from a graph such that the resulting graph consists of highly connected components. We show that Highly Connected Deletion is NP-hard and provide a fixed-parameter algorithm and a kernelization. We propose exact and heuristic solution strategies, based on polynomial-time data reduction rules and integer linear programming with column generation. The data reduction typically identifies 75 percent of the edges that are deleted for an optimal solution; the column generation method can then optimally solve protein interaction networks with up to 6,000 vertices and 13,500 edges within five hours. Additionally, we present a new heuristic that finds more clusters than the method by Hartuv and Shamir.

PubMed Disclaimer

Similar articles

See all similar articles

Cited by

  • Microbial "social networks".
    Fernandez M, Riveros JD, Campos M, Mathee K, Narasimhan G. Fernandez M, et al. BMC Genomics. 2015;16 Suppl 11(Suppl 11):S6. doi: 10.1186/1471-2164-16-S11-S6. Epub 2015 Nov 10. BMC Genomics. 2015. PMID: 26576770 Free PMC article.

Publication types