e-journal

Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage

---

A popular clustering algorithm for biological networks which was proposed by Hartuv and Shamir [5] 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 fixedparameter 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.
Index Terms—Cluster analysis, PPI networks, fixed-parameter tractability, data reduction, integer linear programming, heuristics

---

Ketersediaan

Tidak ada salinan data

Informasi Detail

Judul Seri

IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS

No. Panggil

-

Penerbit

New York : IEEE., 2014

Deskripsi Fisik

IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, VOL. 11, NO. 3, MAY/JUNE 2014

Bahasa

English

ISBN/ISSN

1545-5963

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

VOL. 11, NO. 3, MAY/JUNE 2014

Subjek

TEKNIK

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Yuli/Agus

Versi lain/terkait

Lampiran Berkas

Komentar

---

Anda harus masuk sebelum memberikan komentar