1 What is this page?

This page provides an implementation of the algorithm described by in
"Evolution under reversals: parsimony and conservation of common intervals", IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4(2):301-309, 2007.

This implementation was realised by Yoan Diekmann. It is written in Java 1.5 and is distributed under the GNU General Public License.

Sample data allow to test the algorithm on real genomic data, taken from the GeM Knowledge Database. The permutations the implementation outputs are also available.

2 Download Area

The following archives contain the above mentioned files.

Binary Files (*.class) of PSbR Source Code (*.java) of PSbR Documentation (*.txt)

In addition, a more detailed documentation as the one joined to the implementation will be provided soon. To run the program, the general command and the main options are explained below in Section 3.

3 Running the Program

Once the archive containing the binary files is extracted (tar -xf PSbR_bin.tar), the program can be started using the Java 1.5 Runtime Environment with

java PSbR [-OPTION] [FILE]

The $CLASSPATH environment variable must contain '.' if running it from the actual directory containing the file 'PSbR.class'.

3.1 Help

An explanation of the different options PSbR accepts can be obtained by typing

java PSbR -help

3.2 Manually entered permutations

The execution without any options gives the possibility to enter a permutation manually, simply separate the numbers by a space character.

3.3 Extract permutations from file

java PSbR filename.txt

If the specified file exists and corresponds to the format of the sample-data it is parsed and the permutation is extracted. The resulting permutation is always saved as 'permutation.txt' in the current directory.

3.4 Random and arbitrary permutations

java PSbR -random

java PSbR -arbitrary

These options provide the possibility to test the algorithm on randomly shuffled permutations, or on permutations created by a specified number of arbitrary reversals applied on the identity.

4 Experiments

We performed experiments on mammalian gene order data extracted from GEM with the RBH (reciprocal best hit) method. Here we provide the SQL request we used, the obtained data, and the permutations that are obtained this way.

The RBH method is well adapted to our model, because it provides a one to one correspondance between genes, and then data that are immediately transcribed into permutations. However, it often provides false positives because of duplication events, and there are genes whose position is very unlikely to be the result of a reversal.
We then applied a pre-processing to smooth the permutations by deleting putative false orthologs or genes which position reflects other rearrangement events. The pre-processing consists in the following: if a single gene is found between two blocks of contiguous genes in one permutation while these blocks are direct neighbors in the other permutation, the "intruder" gene is deleted in both permutations.
This preprocessing has been joined to the program, and is done before PSbR if the "-p" option is added to the command.

Here are the data and the permutations we used (text files starting with 'p_' are the permutations modified according to the pre-processing explained above; a file '*_comment.txt' explains eventual further choices to make during the execution to achieve the optimal results).

Sample data (*.txt) Permutations (*.txt)