SPRING: Sorting Permutation by Reversals and block-INterchanGes

Input sequence data:
S1 Vibrio cholerae chromosome II 1.0Mb
S2 Vibrio parahaemolyticus RIMD 2210633 chromosome II 1.8Mb
S3 Vibrio vulnificus YJ016 chromosome II 1.8Mb
Minimum multi-MUM length: 21
Minimum LCB weight: default (which equals to 63)
Rearrangement events: reversals with weight 1 and block-interchanges with weight 2
Chromosome type: circular
Computed common LCB orders:
S1 Vibrio cholerae chromosome II
LCB order1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
S2 Vibrio parahaemolyticus RIMD 2210633 chromosome II
LCB order1 -19 -9 -18 -16 -14 -13 7 5 -12 6 8 -4 10 11 -20 17 -3 15 -2
S3 Vibrio vulnificus YJ016 chromosome II
LCB order1 -19 2 20 -15 3 -17 -16 -9 -18 -13 7 5 -12 6 -8 10 -4 11 -14
Computed breakpoint distance matrix and the corresponding phylogenetic tree:
S1S2S3
S1-1819
S218-12
S31912-
The file of breakpoint distance matrix

The file of breakpoint tree in Newick format
Computed rearrangement distance matrix and the correspoding phylogenetic tree:
S1S2S3
S1-1617
S216-10
S31710-
The file of rearrangement distance matrix

The file of rearrangement tree in Newick format
Optimal scenario of weighted reversals and block-interchanges:
The minimum cost of series for transforming S2 into S1 is 16 which is composed of 16 reversals and 0 block-interchange.
S2(1 -19 -9 -18 -16 -14 -13 7 5 -12 6 8 -4 10 11 -20 17 -3 15 -2)
S1(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
The optimal scenario of weighted reversals and block interchanges is as follows:
S2 =
(1 -19 -9 -18 -16 -14 -13 7 5 -12 6 8 -4 10 11 -20 17 -3 15 -2)
->(1 -19 -9 -18 -16 -14 -13 7 -8 -6 12 -5 -4 10 11 -20 17 -3 15 -2)
->(1 -19 -9 -18 -16 -14 -13 7 8 -6 12 -5 -4 10 11 -20 17 -3 15 -2)
->(1 -19 -9 -18 -16 -14 -13 -8 -7 -6 12 -5 -4 10 11 -20 17 -3 15 -2)
->(1 -19 -9 -18 -16 -14 -13 -12 6 7 8 -5 -4 10 11 -20 17 -3 15 -2)
->(1 -19 -9 -8 -7 -6 12 13 14 16 18 -5 -4 10 11 -20 17 -3 15 -2)
->(1 -19 -18 -16 -14 -13 -12 6 7 8 9 -5 -4 10 11 -20 17 -3 15 -2)
->(1 -19 -18 -16 -14 -13 -12 -9 -8 -7 -6 -5 -4 10 11 -20 17 -3 15 -2)
->(1 -19 -18 -16 -14 -13 -12 4 5 6 7 8 9 10 11 -20 17 -3 15 -2)
->(1 -19 -18 -16 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -20 17 -3 15 -2)
->(1 -19 -18 20 4 5 6 7 8 9 10 11 12 13 14 16 17 -3 15 -2)
->(1 -19 -18 20 -17 -16 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 15 -2)
->(1 18 19 20 -17 -16 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 15 -2)
->(1 -20 -19 -18 -17 -16 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 15 -2)
->(1 -20 -19 -18 -17 -16 3 4 5 6 7 8 9 10 11 12 13 14 15 -2)
->(1 -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2)
=S1

The minimum cost of series for transforming S3 into S1 is 17 which is composed of 17 reversals and 0 block-interchange.
S3(1 -19 2 20 -15 3 -17 -16 -9 -18 -13 7 5 -12 6 -8 10 -4 11 -14)
S1(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
The optimal scenario of weighted reversals and block interchanges is as follows:
S3 =
(1 -19 2 20 -15 3 -17 -16 -9 -18 -13 7 5 -12 6 -8 10 -4 11 -14)
->(1 -2 19 20 -15 3 -17 -16 -9 -18 -13 7 5 -12 6 -8 10 -4 11 -14)
->(1 -2 19 20 -15 3 -17 -16 -9 -18 -13 7 8 -6 12 -5 10 -4 11 -14)
->(1 -2 19 20 -15 3 -17 -16 -9 -18 -13 -8 -7 -6 12 -5 10 -4 11 -14)
->(1 -2 19 20 -15 3 -17 -16 -9 -18 -13 -12 6 7 8 -5 10 -4 11 -14)
->(1 -2 19 20 -15 3 -17 -16 -9 -8 -7 -6 12 13 18 -5 10 -4 11 -14)
->(1 15 -20 -19 2 3 -17 -16 -9 -8 -7 -6 12 13 18 -5 10 -4 11 -14)
->(1 15 -20 -19 2 3 -13 -12 6 7 8 9 16 17 18 -5 10 -4 11 -14)
->(1 15 -20 -19 2 3 -13 -12 -18 -17 -16 -9 -8 -7 -6 -5 10 -4 11 -14)
->(1 15 -20 -19 2 3 -13 -12 -18 -17 -16 5 6 7 8 9 10 -4 11 -14)
->(1 15 -20 -19 2 3 -13 -12 -18 -17 -16 -10 -9 -8 -7 -6 -5 -4 11 -14)
->(1 15 -20 -19 2 3 -13 -12 -18 -17 -16 4 5 6 7 8 9 10 11 -14)
->(1 15 16 17 18 12 13 -3 -2 19 20 4 5 6 7 8 9 10 11 -14)
->(1 15 16 17 18 12 13 -20 -19 2 3 4 5 6 7 8 9 10 11 -14)
->(1 15 16 17 18 19 20 -13 -12 2 3 4 5 6 7 8 9 10 11 -14)
->(1 15 16 17 18 19 20 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -14)
->(1 2 3 4 5 6 7 8 9 10 11 12 13 -20 -19 -18 -17 -16 -15 -14)
=S1

The minimum cost of series for transforming S3 into S2 is 10 which is composed of 10 reversals and 0 block-interchange.
S3(1 -19 2 20 -15 3 -17 -16 -9 -18 -13 7 5 -12 6 -8 10 -4 11 -14)
S2(1 -19 -9 -18 -16 -14 -13 7 5 -12 6 8 -4 10 11 -20 17 -3 15 -2)
The optimal scenario of weighted reversals and block interchanges is as follows:
S3 =
(1 -19 2 20 -15 3 -17 -16 -9 -18 -13 7 5 -12 6 -8 10 -4 11 -14)
->(1 -19 2 20 -15 3 -17 -16 -9 -18 -13 7 5 -12 6 -10 8 -4 11 -14)
->(1 -19 2 20 -15 3 -17 -16 -9 -18 -13 7 5 -12 6 -10 4 -8 11 -14)
->(1 -19 2 20 -15 3 -17 -16 -9 -18 -13 7 5 -12 6 8 -4 10 11 -14)
->(1 -19 2 20 -11 -10 4 -8 -6 12 -5 -7 13 18 9 16 17 -3 15 -14)
->(1 -19 2 -16 -9 -18 -13 7 5 -12 6 8 -4 10 11 -20 17 -3 15 -14)
->(1 -19 2 -15 3 -17 20 -11 -10 4 -8 -6 12 -5 -7 13 18 9 16 -14)
->(1 -19 2 -15 3 -17 20 -11 -10 4 -8 -6 12 -5 -7 13 18 9 -16 -14)
->(1 -19 2 -15 3 -17 20 -11 -10 4 -8 -6 12 -5 -7 13 -9 -18 -16 -14)
->(1 -19 2 -15 3 -17 20 -11 -10 4 -8 -6 12 -5 -7 13 14 16 18 9)
=S2

SPRING by Ying Chih Lin1, Chin Lung Lu2, Ying-Chuan Liu1 and Chuan Yi Tang1
1Department of Computer Science, National Tsing Hua University, Taiwan, ROC.
2Department of Biological Science and Technology, National Chiao Tung University, Taiwan, ROC.
The identified LCBs are computed using a program from Mauve, Copyright © 2003-2005, Aaron Darling
The program for sorting permutation by reversals is derived from a Java applet, Copyright © 1999, Itsik Mantin and Ron Shamir
Back to Input Page