yoshiko and charles

The planet LiSA library is now hosted in "Amsterdam"


yoshiko computes exact solutions to the Cluster Editing problem.

A note on version 2.0

Emanuel Laude did a great job in his Computer Science Bachelor's thesis at the University of Würzburg. Thanks to him, we now have a tool (yoshiko 2.0) that directly combines the redcution rules from fixed parameter algorithmics with the integer linear programming approach as described in S. Böcker, S. Briesemeister, G. W. Klau. Exact algorithms for cluster editing: evaluation and experiments. Algorithmica 60(2):316-334, 2011. Furthermore, yoshiko 2.0 runs on different platforms (Linux, MacOS and Windows) and comes with a powerful heuristic mode.

A note on version 1.5 (yoshiko/charles)

Version 1.5 of our tool also supports transitivity editing in directed graphs, and a previous version of this tool was called charles. Version 2.0 only supports the undirected case (cluster editing), but is much more powerful because of integrated reduction rules from fixed parameter algorithmics. The directed case 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, for example, 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.

warning 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.


version date link description comments
2.0 Aug 13 yoshiko 2.0 reimplementation by Emanuel Laude 64 bit linux executable
2.0 Aug 13 yoshiko 2.0 reimplementation by Emanuel Laude 64 bit MacOS executable
2.0 Aug 13 yoshiko 2.0 reimplementation by Emanuel Laude 64 bit Windows executable
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.

This topic: LiSA > WebLeftBar > YoshikoCharles
Topic revision: 08 Mar 2017, BodoRiedigerKlaus