Exact and Heuristic Algorithms for Weighted Cluster Editing

Sven Rahmann*, Tobias Wittkop, Jan Baumbach, Marcel Martin, Anke Truß, Sebastian Böcker

Computational Methods for Emerging Technologies group, Genome Informatics, Technische Fakultät, Bielefeld University, D-33594 Bielefeld, Germany. Sven.Rahmann@cebitec.uni-bielefeld.de

Proc LSS Comput Syst Bioinform Conf. August, 2007. Vol. 6, p. 391-401. Full-Text PDF

*To whom correspondence should be addressed.

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.