You are here: Wiki>LiSA Web>Scp (18 Jul 2011, GunnarKlau)Edit


Aug 2013
yoshiko version 2.0

We have released yoshiko version 2.0, a mature version of our cluster editing algorithm. It has been implemented mostly by Emanuel Laude and contains a lot of helpful redcution rules from fixed parameter algorithmics and a powerful heuristic for large data sets.

24 Aug 2011
natalie version 2.0

We have released natalie version 2.0, a mature version of our network alignment algorithm.

27 Jun 2011
side chain placement

scp is a package that contains our code for exact side chain placement as used in a recent paper in Optimization Letters.

5 Mar 2010
heinz and BioNet

heinz now works together with the BioNet package.

17 Dec 2008

The yoshiko/charles code is now online. The tool solves the cluster editing problem as well as its directed "cousin", the transitivity editing problem, to provable optimality.

1 Sep 2008
planet lisa moves to Amsterdam

The planet lisa project is now based at the Centre for Mathematics and Computer Science (CWI) in Amsterdam, The Netherlands.

20 Jul 2008
ISMB 2008

Our paper Identifying Functional Modules in Protein-Protein Interaction Data: An Integrated Exact Approach has won the oustanding paper award at ISMB 2008 in Toronto, Canada. See the heinz section for more information on our software to discover optimal subnetworks with respect to our signal-based scoring scheme of p-values.

Jul 2008
ISMB 2008

We will give a presentation at ISMB 2008 on Identifying Functional Modules in Protein-Protein Interaction Data: An Integrated Exact Approach. Our software is available as the heinz package.

Oct 07
Algorithmic Operations Research

Our theoretical lara paper has been accepted for publication in Algorithmic Operations Research.

27 Jul 07
BMC Bioinformatics

The paper describing the lara program has been accepted for publication in BMC Bioinformatics.

28 Jun 07
4SALE support for lara

lara has been integrated into the RNA alignment and editing framework 4SALE. Get the latest lara version that is compatible with 4SALE.



runLagrange [1] is a tool that computes provably optimal solutions to the side-chain placement problem.


warning runLagrange needs to be linked dynamically with BALL 1.2

Quick Start

./runLagrange  [-nopreproc]  [-novarprune]  <lb>|-nolb  <energies_file>


By default the following preprocessing is applied to decrease the size of the problem instance while preserving optimality: (i) Goldstein DEE (see [11] in the paper) (ii) Residue reduction (see [26] in the paper) This preprocessing can be disabled by the option -nopreproc

Furthermore, rotamers that can be proven by the initial primal bound to be suboptimal will be eliminated. Option -novarprune disables this elimination.

Either a primal (lower) bound is given or indicate with -nolb that no such bound is available.


[1] Canzar S, Toussaint NC, Klau GW. An exact algorithm for side-chain placement in protein design. Optim Lett, to appear 2011.


Our development platform is 64 bit Linux. We do not support other platforms. If you are interested in compiling the code on your own to run it on other platforms please contact the authors.

Compiled with g++ (GCC) 4.1.2 for Linux-x86 64 bit.

version date link commentSorted descending
1.0 March 2011 runLagrange 1.0 Version used for the computations in [1]

data date comment
instances March 2011 In [1] we used two benchmark sets. We eliminate, in a preprocessing phase, residues of low degree and rotamers according to Goldstein's dead-end elimination theorem. For details we refer to the paper. All instances are available in the original as well as the preprocessed form upon request (data is too large to download).

Topic revision: r3 - 18 Jul 2011, GunnarKlau
  • Printable version of this topic (p) Printable version of this topic (p)