| Choose a file for download
The BiBiServ team does not provide any support for compiling or using a tool from the download section. Please contact the author directly in case of any problem.
SBBI is a C++ implementation of an improved version of David A. Christie's algorithm for sorting by block-interchanges
(see [Christie 1996]). It runs in time O(n log n) instead of O(n2), as the original version. Please see the implementation
notes for how this is achieved. The program can be used from the command line.
The following is an excerpt from the README file that is includes in the .tar.gz file
Compilation
To compile sbbi, just run make. If there are any problems, look at the Makefile (it is very simple).
Installation
No installation is necessary, just run the program. You can also copy the binary sbbi to a directory that is in your PATH environment variable. A good choice is usually /usr/local/bin/ if that is writable for you.
Running
To see the command-line options, run sbbi -h for help. The input permutations should be provided as a sequence of positive integers, separated by whitespace (space, tab, newline). Since both space and newline can be used, the permutation can be stored in one row, like so:
1 4 2 3 5
and it can also be stored in one 'column', like so:
1
4
2
3
5
Both types can be intermixed:
1 4 2
3 5
In any case, the whole file will be interpreted as just one permutation.
Credits
- Jens Stoye came up with the general idea for the improvement to Christie's algorithm while working with Julia Mixtacki on genome rearrangement problems.
- The implementation was done by Marcel Martin.
- The original algorithm is by David A. Christie [CHR:1996].
- The balanced binary tree is an Andersson tree, introduced by Arne Andersson [AND:1993].
- Independently of our own research, Feng and Zhu [FEN:SHU:2006] proposed the same improvement. They call the data structure a permutation tree. The idea to split the tree into three parts to find the maximum element is taken from their paper. A previous version of our code had its own procedure (doing complicated tree traversals) for doing that.
- The algorithm for splitting and merging balanced binary trees is described by Robert E. Tarjan [Tarjan 1987].
License
The code is MIT-licensed. See the source code
for the complete license text.
|
