TY - JOUR

T1 - Exact and heuristic algorithms for weighted cluster editing.

AU - Rahmann, Sven

AU - Wittkop, Tobias

AU - Baumbach, Jan

AU - Martin, Marcel

AU - Truss, Anke

AU - Böcker, Sebastian

PY - 2007

Y1 - 2007

N2 - Clustering objects according to given similarity or distance values is a ubiquitous problem in computational biology with diverse applications, e.g., in defining families of orthologous genes, or in the analysis of microarray experiments. While there exists a plenitude of methods, many of them produce clusterings that can be further improved. "Cleaning up" initial clusterings can be formalized as projecting a graph on the space of transitive graphs; it is also known as the cluster editing or cluster partitioning problem in the literature. In contrast to previous work on cluster editing, we allow arbitrary weights on the similarity graph. To solve the so-defined weighted transitive graph projection problem, we present (1) the first exact fixed-parameter algorithm, (2) a polynomial-time greedy algorithm that returns the optimal result on a well-defined subset of "close-to-transitive" graphs and works heuristically on other graphs, and (3) a fast heuristic that uses ideas similar to those from the Fruchterman-Reingold graph layout algorithm. We compare quality and running times of these algorithms on both artificial graphs and protein similarity graphs derived from the 66 organisms of the COG dataset.

AB - Clustering objects according to given similarity or distance values is a ubiquitous problem in computational biology with diverse applications, e.g., in defining families of orthologous genes, or in the analysis of microarray experiments. While there exists a plenitude of methods, many of them produce clusterings that can be further improved. "Cleaning up" initial clusterings can be formalized as projecting a graph on the space of transitive graphs; it is also known as the cluster editing or cluster partitioning problem in the literature. In contrast to previous work on cluster editing, we allow arbitrary weights on the similarity graph. To solve the so-defined weighted transitive graph projection problem, we present (1) the first exact fixed-parameter algorithm, (2) a polynomial-time greedy algorithm that returns the optimal result on a well-defined subset of "close-to-transitive" graphs and works heuristically on other graphs, and (3) a fast heuristic that uses ideas similar to those from the Fruchterman-Reingold graph layout algorithm. We compare quality and running times of these algorithms on both artificial graphs and protein similarity graphs derived from the 66 organisms of the COG dataset.

UR - http://www.scopus.com/inward/record.url?scp=37249000536&partnerID=8YFLogxK

U2 - 10.1142/9781860948732_0040

DO - 10.1142/9781860948732_0040

M3 - Article

C2 - 17951842

AN - SCOPUS:37249000536

SN - 1752-7791

VL - 6

SP - 391

EP - 401

JO - Computational systems bioinformatics / Life Sciences Society. Computational Systems Bioinformatics Conference

JF - Computational systems bioinformatics / Life Sciences Society. Computational Systems Bioinformatics Conference

ER -