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.
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.
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'.
An explanation of the different options PSbR accepts can be obtained by typing
java PSbR -help
The execution without any options gives the possibility to
enter a permutation manually, simply separate the numbers by a space
character.
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.
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.
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) |
|
|