:^:home:^:
Reversal Tools

My colleagues and I have written open source code useful for research on whole genome evolution through reversals (inversions).
Among other things, the code...
computes a minimum reversal (inversion) scenario faster than any existing code,
computes an evolutionary scenario using reversals, insertions, and deletions,
displays all minimum reversals scenarios between two genomes as a DAG,
draws the Hannenhalli-Pevzner graph,
and much more...
Use the code at your own risk as it has been used for research only; parts of it were not necessarily written for speed or clarity!
You can browse the README below if you are interested.
The gzipped tar file of the code is here.
Please contact me if you use the code for your project or have any further questions.
The README:


||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|
GENE DISTANCE APPROXIMATION UNDER INSERTIONS, DELETIONS, INVERSIONS, COPIES
There are 4 (documented) sections of functionality:
  A) ANY-to-ANY gene order distances.
  B) Breakpoint graph tools.
  C) Exhaustive (and inefficient) computation of all sorting inversions.
  D) Commuting and Noninterfering inversion computation.

** see the "NOTES" sections to see dependencies that you need to install.
||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|


__A__FOR ANY-to-ANY gene order DISTANCES (and, optionally, sorting sequences):

1) The directories "graph", "multi", "allrevs", "tools", "noninterfering", and
   "seqtools" must reside in the same parent directory (as they are).

2) Use the Makefile in the "multi" directory.
   `-> make in the "multi" directory will create executables called "treeinput",
       "mabrouk", "twoinput", "getdist".

3) The code can be interfaced in three ways...
   a) You can link to the function in multiMED.o :
           int multiMED(int* s1, int ls1, int* s2, int ls2);
           (for an example where this function is used look in multi/twoinput.C 
            or in multi/perfEval.C)

   b) Redirect to "getdist" a file with 2 lines (or interactively), each line
      is a sequence of genes that will be compared.

      -or- (the old way)

      Redirect to "twoinput" a file with 2 lines (or interactively), each line
      is a sequence of genes that will be compared, first elem is 0, second
      element is # of genes, followed by a list of the gene values:
           0 n  s1 s2 s3 ... sn
           0 m  s1' s2' s3' ... sm'

   c) Redirect to "treeinput" or "mabrouk" a file in the format of the sample
      tree-data file in multi/test/:
           #-of-sequences
           (seq0)                                 [the sequences]
           (seq1)
             .
             .
             .
           (seqn)
           done
           (seqx . seqy) true-tree-distance
             .                                    [every pair of sequences]
             .
             .
           (seqx . seqy) true-tree-distance
           done


-- If multiMED() is used, the approximate Minimum Edit Distance is returned.
--
-- Otherwise, the results are printed to stdout, the last line of the output is
-- "Edit-Dist:xxx" where xxx is the calculated edit distance.

4) ADDITIONAL FEATURES:

 - If you are not interested in generating a sorting sequence between genomes,
   you can either comment out the SORTING_SEQUENCE define in multi/SortSeq.h or
   set the global pointer globalSortSequence to NULL. Commenting out the define
   may significantly reduce the size of the executable.

 - If you want to obtain the distance based on the El-Mabrouk method (no copies)
   uncomment the 'MABROUK' directive.


NOTES:
 - This code requires the Standard Template Library (shouldn't be a problem).
   [ http://www.sgi.com/tech/stl/ ]
   Ubuntu package: libstlport
  - This code requires the libboost-graph packages.
    Ubuntu package: libboost-graph-dev
  - This code requires the igraph packages.
    Add the lines to /etc/apt/sources.list:
      deb http://ppa.launchpad.net/igraph/ppa/ubuntu jaunty main
      deb-src http://ppa.launchpad.net/igraph/ppa/ubuntu jaunty main
    Install packages: libigraph-dev and libigrpah0
   
CHANGES:
 (2006-2-13)
 - Added Ograph function to output an SVG of the breakpoint graph.
 (2006-1-1)
 - Updated to compile with gcc 4.
 (2004-4-27)
 - El-Mabrouk distance support added (for comparison purposes).
 (2004-2-28)
 - Sorting sequence support added.
 (2003-10-8)
 - Resolves Hurdles.




||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|


__B__BREAKPOINT GRAPHS TOOLS:
1) Go to the "seqtools" directory.
2) Use the Makefile.
   `-> 'make' in "seqtools" will create executables.

-svg picture of a breakpoint graph...
  Give "getgraph" a space delimited permutation of the identity sequence
   (for example "3 5 4 2 -1 9 -8 7 6").
-compair two sequences for any difference...
  Give "compair" two space delimited strings
-rename two permuations so that the first is the identity...
  Give "rename" two space delimited permutations of the identity sequence
-get a substring of the given sequence...
  Give "seqviewer" a space delimited string
-print the inverse permutation of the given one...
  Give "inverse" a space delimited permutation of the identity sequence
-print the HP cycles of the the given permutation...
  Give "getcycles" a space delimited permutation of the identity sequence
-print the orientations of the reality edges...
  Give "getorientations" a space delimited permutation of the identity sequence
-print the interfering inversions associated with a reality edge...
  Give "getinterfering" a space delimited permutation of the identity sequence

CHANGES:
  (2007-9-25)
  - Added the "get_______" executables.
  (2006-8-1)
  - Moved getgraph to the seqtools directory.
  (2006-2-13)
  - Inception of getgraph.

NOTES:
  - This code requires the libboost-graph packages.
    Ubuntu package: libboost-graph-dev
  - This code requires the igraph packages.
    Add the lines to /etc/apt/sources.list:
      deb http://ppa.launchpad.net/igraph/ppa/ubuntu jaunty main
      deb-src http://ppa.launchpad.net/igraph/ppa/ubuntu jaunty main
    Install packages: libigraph-dev and libigrpah0
  - The "seqtools/getgraph" script requires "ksvg" to be installed.




||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|


__C__TO GENERATE GRAPHS OF ALL POSSIBLE SORTING SEQUENCES:

1) Use the Makefile in the "allrevs" directory.
   `-> make in the "allrevs" directory will create executable called "allrevs"
2a) Use "showlattice".
  -- or --
2b) Direct the output of "allrevs" to a file (%allrevs > graph.dot).
3b) OPTIONAL: remove duplicate links with "removedups" (%removedups graph.dot).
4b) Create the graph with graphviz's "dot" (dot -Tps graph.dot -o graph.ps).

CHANGES:
  (2006-2-1)
  - Inception.

NOTES:
  - This code requires the graphviz package.
    [ http://www.research.att.com/sw/tools/graphviz/ ]
  - This code requires the igraph packages.
    Add the lines to /etc/apt/sources.list:
      deb http://ppa.launchpad.net/igraph/ppa/ubuntu jaunty main
      deb-src http://ppa.launchpad.net/igraph/ppa/ubuntu jaunty main
    Install packages: libigraph-dev and libigrpah0



||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|||!!:-:!!|


__D__TO GET MAXIMUM SETS OF COMMUTING AND NONINTERFERING INVERSION:

1) Go to directory "noninterfering" and type make.
2) "maxnint" asks for two permutations and returns a maximum set of
   mutually commuting inversions.
3) "maxnints" returns a maximum set of commuting inversions for the given
   permutation.
4) "trygraphs" and "trymutual" excersize the noninterfering inversion
   computations by giving them random permutations.


NOTES:
  - This code requires the igraph packages.
    Add the lines to /etc/apt/sources.list:
      deb http://ppa.launchpad.net/igraph/ppa/ubuntu jaunty main
      deb-src http://ppa.launchpad.net/igraph/ppa/ubuntu jaunty main
    Install packages: libigraph-dev and libigrpah0

CHANGES:
  (2008-3-1)
  - Inception.