The graphical representation of this breakpoint graph follows (the unique arbitrary number of each long cycle is indicated):
baobabLUNA: the solution space of sorting by reversals
The package baobabLUNA is a java framework to deal with
permutations that represent genomes in rearrangement analysis.
baobabLUNA contains a collection of classes for building
breakpoint graphs (the basic structures behind the
work on genome rearrangements), performing reversals, calculating
reversal distances, sorting permutations. Includes a text
representation for the breakpoint graph
(class baobab.bio.permutation.PermutationBPGraphFormatter).
baobabLUNA is only able to deal with unichromosomal genomes and its main functionality is the implementation of an algorithm that gives a compact representation of the space of all solutions of the sorting by reversals problem, that is, a representation of all optimal sequences of reversals that sort one genome into another.
A reduced on-line documentation of baobabLUNA (with some interface aspects and tutorial of executable programs) is offered in this website (see bellow). A full documentation (with complete methodological background, technical aspects, interface description, download & setup instructions and tutorial of executable programs) is provided in PDF format here. We also provide download of compiled code and java API.
Developed by Marília D. V. Braga
Preliminary version - last update November 2008
2.1. Interface aspects: the text representation
for the breakpoint graph
The breakpoint graph is represented by a string with four lines. The first,
the second and the third lines represent the cycles' black and gray edges
(... represents an adjacency). The fourth line contains the given origin
permutation.
Example: for the linear permutation -4,-3,12,-11,-8,10,9,7,-6,-5,2,-1, we have the following text representation of its breakpoint graph:
01. 02. 03. 04. 05. 06. 07. 08. 09. 10. 11. 12. 13. [A] 01> ... 01> <01 03> <02 <03 <02 02> ... 01> <01 <01 [B] :11 ... :04 :13 :07 :09 :05 :06 :08 ... :12 :03 :01 [C] :: -04 -03 +12 -11 -08 +10 +09 +07 -06 -05 +02 -01 :: 5 cycles [D][A] Black edges' index line: the black edges are numbered in increasing order.
[B] Black edges' direction: each black edge receives a direction, according to an arbitrary tour in the corresponding cycle (each cycle receives a unique arbitrary number, thus two edges with the same numbers are in the same cycle).
[C] Gray edges: each cycle tour in the direction induced by black edges' direction (the number after the ":" indicates the next black edge to be visited, referring to the [first] index line).
[D] Permutation line: the given permutation and the number of cycles (adjacencies + long cycles) in the corresponding breakpoint graph.
The graphical representation of this breakpoint graph follows (the unique arbitrary number of each long cycle is indicated):
The text representation of breakpoint graphs is largely used in our executable programs. It is implemented by the class baobab.bio.permutation.PermutationBPGraphFormatter (consult the class API to get a description of its usability).
2.2. List of executable programs and tutorial
2.2.1. A list of programs which deal with permutations
2.2.2. A program to generate a representation of the space of all solutions for the sorting by reversals problem (and the modified versions, which filter solutions using constraints)
2.2.3. Examples (tutorial)
2.2.1. A list of programs which deal with permutations
package baobab.exec.permutation
package baobab.exec.trace
Attention: the number of traces may be huge for permutations with reversal distance greater than 12. During its execution, the program has to keep a considerable amount of data, but its intern organization allows automatic partial and required global compression of this data (there are parameters to set the level of compression).
Applying biological constraints
When biological constraints are applied, the program analyzes the
space of all sorting sequences that respect the given constraints only.
It returns the list of non-empty traces that are in agreement with the
constraints.
To get the help, run the program without arguments.
|
|
>java -classpath baobab-luna.jar baobab.exec.permutation.sort
Sorts the given signed permutation (this program does not deal with hurdles)
Required parameters:
-o originPermutation (values separated by commas, without spaces)
Ex: -o -4,-3,12,-11,-8,10,9,7,-6,-5,2,-1
Optional parameters:
-t targetPermutation (values separated by commas, without spaces)
Ex: -t 5,-3,12,10,9,8,-11,7,-6,-4,2,-1
-l T/F (T=linear [default], F=circular)
Ex: -l F
|
|
Example - Sorting the linear permutation -3 +2 +1 -4:
>java -classpath baobab-luna.jar baobab.exec.permutation.sort -o -3,2,1,-4
1. 2. 3. 4. 5.
1> <1 1> <1 1>
:5 :3 :1 :2 :4
:: -3 +2 +1 -4 :: 1 cycles
Reversal distance: 4
Solution:
1. 2. 3. 4. 5.
1> <1 1> <1 1>
:5 :3 :1 :2 :4
:: -3 +2 +1 -4 :: 1 cycles
--- (from [1] -3 to -3 [2])
1. 2. 3. 4. 5.
2> <1 2> <1 1>
:3 :5 :1 :2 :4
:: +3 +2 +1 -4 :: 2 cycles
--------- (from [2] +2 to -4 [5])
1. 2. 3. 4. 5.
2> .. 1> <2 1>
:4 .. :5 :1 :3
:: +3 +4 -1 -2 :: 3 cycles
--------- (from [1] +3 to -1 [4])
1. 2. 3. 4. 5.
.. <1 .. .. 1>
.. :5 .. .. :2
:: +1 -4 -3 -2 :: 4 cycles
--------- (from [2] -4 to -2 [5])
1. 2. 3. 4. 5.
.. .. .. .. ..
.. .. .. .. ..
:: +1 +2 +3 +4 :: 5 cycles
|
|
Example - Sorting the circular permutation -3 +2 +1 -4 (observe that the circular permutations -3 +2 +1 -4 and -1 -2 +3 +4 are equivalent):
>java -classpath baobab-luna.jar baobab.exec.permutation.sort -l F -o -3,2,1,-4
1. 2. 3. 4.
1> <1 1> ..
:3 :1 :2 ..
:: -1 -2 +3 +4 :: 2 cycles
Reversal distance: 2
Solution:
1. 2. 3. 4.
1> <1 1> ..
:3 :1 :2 ..
:: -1 -2 +3 +4 :: 2 cycles
--- (from [1] -1 to -1 [2])
1. 2. 3. 4.
.. <1 1> ..
.. :3 :2 ..
:: +1 -2 +3 +4 :: 3 cycles
--- (from [2] -2 to -2 [3])
1. 2. 3. 4.
.. .. .. ..
.. .. .. ..
:: +1 +2 +3 +4 :: 4 cycles
|
|
Example - Calculating the reversal distance of the permutation +23 +22 +1 +4 +7 +10 +9 +8 +11 +6 +5 +12 +15 +18 +17 +16 +19 +14 +13 +20 +3 +2 +21 (a fortress - 12 cycles, 6 unoriented components, no oriented components, 3 super-hurdles, no simple-hurdles):
>java -classpath baobab-luna.jar baobab.exec.permutation.analyzeSignedPermutation -o 23,22,1,4,7,10,9,8,11,6,5,12,15,18,17,16,19,14,13,20,3,2,21 01. 02. 03. 04. 05. 06. 07. 08. 09. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 01> 12> 01> 02> 04> 06> 07> 06> 07> 05> 04> 05> 08> 10> 11> 10> 11> 09> 08> 09> 03> 02> 03> 12> :03 :24 :01 :22 :11 :08 :09 :06 :07 :12 :05 :10 :19 :16 :17 :14 :15 :20 :13 :18 :23 :04 :21 :02 :: +23 +22 +01 +04 +07 +10 +09 +08 +11 +06 +05 +12 +15 +18 +17 +16 +19 +14 +13 +20 +03 +02 +21 :: 12 cycles Reversal distance: 16
|
|
Example - Performing reversals on the permutation -4 -3 +12 -11 -8 +10 +9 +7 -6 -5 +2 -1:
>java -classpath baobab-luna.jar baobab.exec.permutation.performReversals -o -4,-3,12,-11,-8,10,9,7,-6,-5,2,-1 -r "11,13|3,13"
01. 02. 03. 04. 05. 06. 07. 08. 09. 10. 11. 12. 13.
01> ... 01> <01 03> <02 <03 <02 02> ... 01> <01 <01
:11 ... :04 :13 :07 :09 :05 :06 :08 ... :12 :03 :01
:: -04 -03 +12 -11 -08 +10 +09 +07 -06 -05 +02 -01 :: 5 cycles
Reversal distance: 8
Reversals:
01. 02. 03. 04. 05. 06. 07. 08. 09. 10. 11. 12. 13.
01> ... 01> <01 03> <02 <03 <02 02> ... 01> <01 <01
:11 ... :04 :13 :07 :09 :05 :06 :08 ... :12 :03 :01
:: -04 -03 +12 -11 -08 +10 +09 +07 -06 -05 +02 -01 :: 5 cycles
-------- (from [11] +02 to -01 [13])
01. 02. 03. 04. 05. 06. 07. 08. 09. 10. 11. 12. 13.
04> ... 01> <01 03> <02 <03 <02 02> ... 04> 01> <01
:11 ... :04 :13 :07 :09 :05 :06 :08 ... :01 :03 :12
:: -04 -03 +12 -11 -08 +10 +09 +07 -06 -05 +01 -02 :: 6 cycles
---------------------------------------- (from [03] +12 to -02 [13])
01. 02. 03. 04. 05. 06. 07. 08. 09. 10. 11. 12. 13.
04> ... 05> <05 <04 ... <02 02> 03> 02> <03 01> <01
:05 ... :04 :03 :01 ... :08 :10 :11 :07 :09 :13 :12
:: -04 -03 +02 -01 +05 +06 -07 -09 -10 +08 +11 -12 :: 7 cycles
|
|
Example - Analyzing the traces of the permutation -3 +2 +1 -4:
>java -classpath baobab-luna.jar baobab.exec.trace.analyzeTraces -o -3,2,1,-4
1. 2. 3. 4. 5.
1> <1 1> <1 1>
:5 :3 :1 :2 :4
:: -3 +2 +1 -4 :: 1 cycles
summary:
Reversal distance: 4
Total number of 4-traces: 2
Total number of solutions: 28
Distribution by height:
Height=1: 1 traces; 24 solutions
Height=3: 1 traces; 4 solutions
Distribution by width:
Width=2: 1 traces
Width=4: 1 traces
The first biggest trace follows:
{1}{1.-.3}{2}{4} : h=1 [24]
4-traces:
{1}{1.-.3}{2}{4} : h=1 [24] w=4
{1.2.4}{3} < {1.3.4} < {2.-.4} : h=3 [4] w=2
Number of 4-traces: 2
Solutions computed by 4-traces: 28
|
|
Example - Analyzing the traces of the permutation -4 -3 +12 -11 -8 +10 +9 +7 -6 -5 +2 -1:
>java -classpath baobab-luna.jar baobab.exec.trace.analyzeTraces -o -4,-3,12,-11,-8,10,9,7,-6,-5,2,-1
01. 02. 03. 04. 05. 06. 07. 08. 09. 10. 11. 12. 13.
01> ... 01> <01 03> <02 <03 <02 02> ... 01> <01 <01
:11 ... :04 :13 :07 :09 :05 :06 :08 ... :12 :03 :01
:: -04 -03 +12 -11 -08 +10 +09 +07 -06 -05 +02 -01 :: 5 cycles
summary
Reversal distance: 8
Total number of 8-traces: 6
Total number of solutions: 31752
Distribution by height:
Height=2: 3 traces; 30240 solutions
Height=4: 3 traces; 1512 solutions
Distribution by width:
Width=4: 3 traces
Width=6: 3 traces
The first biggest trace follows:
{1.2}{1.2.5.-.12}{2}{7}{8.10}{12} < {1.-.4}{8.9} : h=2 [10080]
8-traces
{1.2}{1.2.5.-.12}{2}{7}{8.10}{12} < {1.-.4}{8.9} : h=2 [10080] w=6
{1.-.12}{2}{3.4.12}{5.-.11}{7}{8.10} < {3.-.11}{8.9} : h=2 [10080] w=6
{1.-.12}{2.-.12}{2.5.-.12}{7}{8.10}{12} < {2.-.4}{8.9} : h=2 [10080] w=6
{1.2}{7}{8.10} < {1.5.-.11}{8.9} < {1.3.4.12} < {2.-.12}{3.-.11} : h=4 [336] w=4
{2.-.12}{7}{8.10} < {1.3.4.12}{8.9} < {1.5.-.11} < {1.2}{3.-.11} : h=4 [336] w=4
{2.5.-.12}{5.-.11}{7}{8.10} < {1.12}{8.9} < {1.5.-.11} < {1.-.4} : h=4 [840] w=4
Number of 8-traces: 6
Solutions computed by 8-traces: 31752
Example - Analyzing the perfect traces of the permutation -5,-2,-7,4,-8,3,6,-1:
(perfect traces are those whose solutions do not break the initially detected common intervals of a permutation)
>java -classpath baobab-luna.jar baobab.exec.trace.analyzeTraces -p -1 -o -5,-2,-7,4,-8,3,6,-1
1. 2. 3. 4. 5. 6. 7. 8. 9.
1> <1 1> <1 1> 1> <1 1> <1
:7 :5 :6 :8 :9 :2 :4 :3 :1
:: -5 -2 -7 +4 -8 +3 +6 -1 :: 1 cycles
summary:
Reversal distance: 8
8-traces:
{1.-.8}{2}{2.-.5.7.8}{2.4.7} < {2.3.7.8}{2.8} < {2.-.6}{7.8} : [1288]
{1.-.8}{2}{2.-.5.7.8}{2.4.7}{3.8} < {2.4.-.7}{4.-.6} < {3.-.7} : [2072]
...
{1.-.8}{2.4.7.8} < {2.-.4.6.7} < {2.3.5.-.8} < {2.-.6.8} < {4.5.7.8} < {4.6.7} < {5.-.7} : [8]
{1.-.8}{3.4.6.8} < {2.6.7} < {2.-.4.8} < {4.6.7} < {3.6.-.8} < {3.-.5.8} < {3.-.7} : [8]
Total number of 8-traces: 92
Total number of solutions: 51304
|
|
Example - Analyzing the progressive perfect subtraces of the permutation -5,-2,-7,4,-8,3,6,-1:
(progressive perfect subtraces are those whose solutions do not break the progressively detected common intervals of a permutation)
>java -classpath baobab-luna.jar baobab.exec.trace.analyzeTraces -p 0 -o -5,-2,-7,4,-8,3,6,-1
1. 2. 3. 4. 5. 6. 7. 8. 9.
1> <1 1> <1 1> 1> <1 1> <1
:7 :5 :6 :8 :9 :2 :4 :3 :1
:: -5 -2 -7 +4 -8 +3 +6 -1 :: 1 cycles
summary:
Reversal distance: 8
8-traces:
{1.-.8}{2}{2.-.5.7.8}{2.4.-.7}{3.8}{2.4.7}{4.-.6}{3.-.7} (representative)
{1.-.8}{2}{2.-.5.7.8}{2.4.7}{3.8} < {2.4.-.7}{4.-.6} < {3.-.7} (normal form)
[112] (size)
{1.-.8}{2}{2.-.5.7.8}{3.8}{4}{3.4.7}{2.-.4}{2.-.6} (representative)
{1.-.8}{2}{2.-.5.7.8}{3.8}{4} < {3.4.7} < {2.-.4}{2.-.6} (normal form)
[1344] (size)
...
{1.-.8}{2.-.5.7.8}{2.4.-.7}{2.3.5.-.8}{2.-.6.8}{3.4.7.8}{3.-.7}{5.-.7} (representative)
{1.-.8}{2.-.5.7.8} < {2.4.-.7} < {2.3.5.-.8} < {2.-.6.8} < {3.4.7.8} < {3.-.7}{5.-.7} (normal form)
[16] (size)
Total number of 8-subtraces: 12
Total number of solutions: 11568
Example - Analyzing the strata-induced subtraces of the permutation -4 -3 +12 -11 -8 +10 +9 +7 -6 -5 +2 -1, with the strata end points at positions (points) 03., 11. and 13.:
>java -classpath baobab-luna.jar baobab.exec.trace.analyzeTraces -s 3,11,13 -o -4,-3,12,-11,-8,10,9,7,-6,-5,2,-1
01. 02. 03. 04. 05. 06. 07. 08. 09. 10. 11. 12. 13.
01> ... 01> <01 03> <02 <03 <02 02> ... 01> <01 <01
:11 ... :04 :13 :07 :09 :05 :06 :08 ... :12 :03 :01
:: -04 -03 +12 -11 -08 +10 +09 +07 -06 -05 +02 -01 :: 5 cycles
summary
Reversal distance: 8
Strata end points:
> 3 (between -3 and 12)
> 11 (between -5 and 2)
> 13 (after -1)
Total number of 8-traces: 1
Total number of solutions: 420
Distribution by height:
Height=2: 1 traces; 420 solutions
Distribution by width:
Width=6: 1 trace
The first biggest trace follows:
{1.2}{1.2.5.-.12}{2}{7}{8.10}{12} < {1.-.4}{8.9} : h=2 [420]
8-traces
{1.2}{1.2.5.-.12}{2}{7}{8.10}{12} < {1.-.4}{8.9} : h=2 [420] w=6
Number of 8-traces: 1
Solutions computed by 8-traces: 420
Here you can download the full compiled code (including executables) and the API documentation with the list of classes and functionalities of the package baobab.bio.permutation only.