yoshiko and charles

yoshiko computes exact solutions to the Cluster Editing problem and the Transitivity Editing problem, respectively.

A note on charles

Charles has been merged with yoshiko, because it appears as a special case.

The tool is described in the paper "On optimal comparability editing with applications to molecular diagnostics" (BMC Bioinformatics, 2009) with Sebastian Böcker from Jena and Sebastian Briesemeister from Tübingen. Note that the title is misleading as a better name for these problems is Transitivity Editing. The Transitivity Editing problem appears in the context of hierarchical disease classification based on noisy data. We are given a directed graph G representing hierarchical relationships between patient subgroups. The task is to identify the minimum number of edge insertions or deletions to transform G into a transitive graph, that is, if edges (u, v) and (v, w) are present then edge (u, w) must be present, too.

The data we used in our paper will be provided upon request.

Please note that you need a CPLEX license to run charles. However, the tool based on fixed-parameter algorithmics does not need such a license and can be found here.

If you experience problems with the code please contact Gunnar Klau.

---

Download

version	date	link	description	comments
1.5	Dec 08	yoshiko/charles 1.5	version used for computations in our APBC paper (BMC Bioinformatics)	This is a 64 bit linux executable.
	Dec 08		data used in our APBC paper	The file exceeds the 10MB limit of this TWiki system. It is available upon request.