Exact and heuristic algorithms for weighted cluster editing.

Sven Rahmann, Tobias Wittkop, Jan Baumbach, Marcel Martin, Anke Truss, Sebastian Böcker

Research output: Contribution to journalArticlepeer-review

52 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)391-401
Number of pages11
JournalComputational systems bioinformatics / Life Sciences Society. Computational Systems Bioinformatics Conference
Volume6
DOIs
StatePublished - 2007
Externally publishedYes

Fingerprint

Dive into the research topics of 'Exact and heuristic algorithms for weighted cluster editing.'. Together they form a unique fingerprint.

Cite this