## 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.

- Full documentation in PDF format: complete methodological background, technical aspects, interface description, download & setup instructions and tutorial of executable programs.
- On-line documentation

2.1. Interface aspects: the text representation for the breakpoint graph

2.2. List of programs and tutorial - A list of programs which deal with permutations
- 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)
- Examples (tutorial)
- Download (Compiled code & Java API)
- References

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

- analyzeSignedPermutation: analyzes a signed permutation and prints its breakpoint graph and reversal distance
- analyzeUnsignedPermutation: analyzes an unsigned permutation and prints its breakpoint graph
- collapsePermutation: collapses a breakpoint graph of a signed permutation to eliminate its adjacencies
- decomposeSignedPermutation: decomposes a breakpoint graph of a signed permutation into its components
- getComplexFirstReversals: finds all optimal reversals for the given signed permutation (this program deals with hurdles, but does not deal with a fortress)
- getFirstOrientedReversals: finds all optimal reversals for the given signed permutation (this program does not deal with hurdles)
- performReversals: perform the reversals (defined by their beginning and end points) in the given order
- sort: sorts the given signed permutation (this program deals with hurdles, but does not deal with a fortress)

package baobab.exec.trace

- analyzeTraces: Analyzes the space of all solutions for the sorting by reversals problem for the given signed permutation - a trace represents a class of solutions. This program enumerates all traces without enumerating all solutions, and counts the number of solutions represented by each trace. It returns the list of traces represented by their normal forms and the respective number of solutions in each trace (this program does not deal with hurdles). The algorithm is described in [4],[5].
- Analyzing the traces whose solutions do not break the initially detected common
intervals between the two given permutations (perfect traces): the parameter
`-p -1`may be given. The version of this program that accepts common interval breaks is not implemented in baobabLUNA. - Analyzing the traces whose solutions do not break the progressively detected common
intervals between the two given permutations (progressive perfect subtraces), accepting
at most
`i>=0`common interval breaks: the parameter`-p i`may be given. - Analyzing the strata-induced subtraces of a permutation: the permutation
must be linear, the first stratum is assumed to start in point 1, then each
stratum starts in the end point of the previous stratum. The strata end
points may be given by the following parameter:
`-s [points]`(points may be separated by commas, without spaces). Example:`-s 7,15,23`. This version is described in [5].

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.

- Getting help
- Sorting a linear signed permutation
- Sorting a circular signed permutation
- Calculating the reversal distance of a linear signed permutation
- Performing reversals on a linear signed permutation
- Analyzing the traces of a linear signed permutation (1)
- Analyzing the traces of a linear signed permutation (2)
- Analyzing the traces whose solutions do not break the initially detected common intervals of a linear signed permutation (perfect traces)
- Analyzing the traces whose solutions do not break the progressively detected common intervals of a linear signed permutation (progressive perfect subtraces)
- Analyzing the strata-induced subtraces of a linear signed permutation

>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.

Version 1.1 beta (21/Nov/2008)

Executable, lib (jar) >> baobab-luna.jar

Documentation (API) >> baobab-luna-api.tar.gz

Version 1.0 beta (28/Apr/2008)

Executable, lib (jar) >> baobab-luna-1.0beta.jar

Documentation (API) >> baobab-luna-api-1.0beta.tar.gz

Version 0.4 beta (01/Aug/2007)

Executable, lib (jar) >> baobab-luna-0.4beta.jar

Documentation (API) >> baobab-luna-api-0.4beta.tar.gz

Version 0.3 beta (02/Mar/2007)

Executable, lib (jar) >> baobab-luna-0.3beta.jar

Documentation (API) >> baobab-luna-api-0.3beta.tar.gz

Version 0.2 beta (22/Nov/2006)

Executable, lib (jar) >> baobab-luna-0.2beta.jar

Documentation (API) >> baobab-luna-api-0.2beta.tar.gz

Version 0.1 beta (15/Nov/2006)

Executable, lib (jar) >> baobab-luna-0.1beta.jar

Documentation (API) >> baobab-luna-api-0.1beta.tar.gz

- Braga M. D. V., Gautier C. and Sagot M-F., An asymmetric approach to preserve common intervals while sorting by reversals, Algorithms for Molecular Biology, 2009.
- Braga M. D. V., babobabLUNA: the solution space of sorting by reversals, Bioinformatics, vol. 25, no. 14, 1833--1835, 2009.
- Braga M. D. V., Exploring the solution space of sorting by reversals when analyzing genome rearrangements. PhD thesis, 2009. Available here.
- Braga M. D. V, Sagot M.-F., Scornavacca C. and Tannier E., Exploring The Solution Space of Sorting by Reversals With Experiments and an Application to Evolution, Transactions on Computational Biology and Bioinformatics, vol. 5, no. 3, 348--356, 2008.
- Braga M. D. V, Sagot M.-F., Scornavacca C. and Tannier E., The Solution Space of Sorting by Reversals, ISBRA 2007,
*Lecture Notes in Bioinformatics*4463, 293-304, 2007. - Bergeron A., Chauve C., Hartmann T., St-Onge K., On the properties of sequences of reversals that sort a signed permutation. JOBIM 2002, 99-108.
- Hannenhalli, S. and Pevzner, P. A. Transforming cabagge into turnip (polynomial algorithm for sorting signed permutations by reversals). In Proceedings of the 27th Annual ACM-SIAM Symposium on the Theory of Computing, pages 178-189, 1995.
- Hannenhalli, S. and Pevzner, P. A. Transforming men into mice (polynomial algorithm for genomic distance problem). In Proceedings of the IEEE 36th Annual Symposium on Foundations of Computer Science, pages 581-592, 1995.
- Java

Developed by Marília D. V. Braga

Preliminary version - last update November 2008