SPRING

SPRING: Sorting Permutation by Reversals and block-INterchanGes

Input sequence data:

S1	Escherichia coli O157:H7 EDL933	5.5Mb
S2	Escherichia coli K12	4.6Mb
S3	Escherichia coli O157:H7	5.4Mb
S4	Escherichia coli CFT073	5.2Mb
S5	Shigella flexneri 2a 301	4.6Mb
S6	Shigella flexneri 2a 2457T	4.5Mb
S7	Salmonella typhimurium LT2	4.8Mb
S8	Salmonella enterica subsp. enterica serovar CT18	4.8Mb
S9	Salmonella enterica subsp. enterica serovar Typhi Ty2	4.7Mb
S10	Yersinia pestis CO92	4.6Mb
S11	Yersinia pestis KIM	4.6Mb

Minimum multi-MUM length: 23

Minimum LCB weight: default (which equals to 69)

Rearrangement events: reversals with weight 1 and block-interchanges with weight 2

Chromosome type: circular

Computed common LCB orders:

S1	Escherichia coli O157:H7 EDL933
LCB order	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
S2	Escherichia coli K12
LCB order	1 2 3 4 5 6 7 8 9 10 11 12 13 -14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
S3	Escherichia coli O157:H7
LCB order	1 2 3 4 5 6 7 8 9 10 11 12 13 -14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
S4	Escherichia coli CFT073
LCB order	1 2 3 4 5 6 7 8 9 10 11 12 13 -14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
S5	Shigella flexneri 2a 301
LCB order	1 2 3 4 5 -7 -6 8 9 10 11 12 13 -14 -19 -18 -17 -16 15 20 21 22 23 24 25 26 27 28 29 -30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 -47 48 49 50 51 52 53 54 -57 55 56 58
S6	Shigella flexneri 2a 2457T
LCB order	1 2 3 4 5 -7 -6 8 9 10 11 12 13 -14 -19 -18 -17 -16 15 20 21 22 23 24 25 26 27 28 29 -30 31 32 33 34 35 36 37 38 39 40 -54 -53 -52 -51 -50 -49 -48 47 -46 -45 -44 -43 -42 -41 -57 55 56 58
S7	Salmonella typhimurium LT2
LCB order	1 2 3 4 5 6 7 8 9 10 -17 -16 -15 14 -13 -12 -11 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
S8	Salmonella enterica subsp. enterica serovar CT18
LCB order	1 2 3 4 5 6 7 8 9 10 12 13 -14 15 16 17 -11 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 -49 -54 -53 -52 -51 -50 -48 -47 -46 -45 -44 -43 -42 -41 55 56 57 58
S9	Salmonella enterica subsp. enterica serovar Typhi Ty2
LCB order	1 2 3 -29 -28 -27 -26 -25 -24 -23 -22 -21 -20 -19 -18 11 -17 -16 -15 14 -13 -12 -10 -9 -8 -7 -6 -5 -4 30 31 32 33 34 35 36 37 38 39 40 -49 -54 -53 -52 -51 -50 -48 -47 -46 -45 -44 -43 -42 -41 55 56 57 58
S10	Yersinia pestis CO92
LCB order	50 -45 52 -41 55 58 1 -36 35 -34 3 4 -32 7 -23 9 -22 10 -19 -18 -21 11 -20 -17 12 13 -14 15 16 -8 24 6 -29 -25 28 -26 27 -5 30 31 33 -2 -57 38 -56 37 39 -40 -54 42 -49 -53 43 -46 51 44 47 48
S11	Yersinia pestis KIM
LCB order	45 37 39 40 52 53 49 -42 54 55 56 -38 57 2 -33 -31 -30 5 6 -29 -28 -27 26 -25 -24 8 10 -19 -16 -15 13 -14 -12 17 20 -11 21 18 22 -9 23 -7 32 -4 -3 34 35 36 -1 -58 -50 -43 -41 -46 51 44 47 48

Computed breakpoint distance matrix and the corresponding phylogenetic tree:

	S1	S2	S3	S4	S5	S6	S7	S8	S9	S10	S11
S1	-	2	2	2	13	14	4	9	11	51	43
S2	2	-	0	0	12	13	2	7	9	49	42
S3	2	0	-	0	12	13	2	7	9	49	42
S4	2	0	0	-	12	13	2	7	9	49	42
S5	13	12	12	12	-	2	14	18	19	53	47
S6	14	13	13	13	2	-	15	18	19	53	47
S7	4	2	2	2	14	15	-	6	8	49	42
S8	9	7	7	7	18	18	6	-	2	47	43
S9	11	9	9	9	19	19	8	2	-	48	44
S10	51	49	49	49	53	53	49	47	48	-	23
S11	43	42	42	42	47	47	42	43	44	23	-
The file of breakpoint distance matrix

The file of breakpoint tree in Newick format

Computed rearrangement distance matrix and the correspoding phylogenetic tree:

	S1	S2	S3	S4	S5	S6	S7	S8	S9	S10	S11
S1	-	1	1	1	8	9	2	6	7	37	33
S2	1	-	0	0	7	8	1	5	6	36	32
S3	1	0	-	0	7	8	1	5	6	36	32
S4	1	0	0	-	7	8	1	5	6	36	32
S5	8	7	7	7	-	1	8	12	13	43	39
S6	9	8	8	8	1	-	9	11	12	42	40
S7	2	1	1	1	8	9	-	4	5	35	31
S8	6	5	5	5	12	11	4	-	1	35	33
S9	7	6	6	6	13	12	5	1	-	36	34
S10	37	36	36	36	43	42	35	35	36	-	15
S11	33	32	32	32	39	40	31	33	34	15	-
The file of rearrangement distance matrix

The file of rearrangement tree in Newick format

SPRING by Ying Chih Lin¹, Chin Lung Lu ², Ying-Chuan Liu¹ and Chuan Yi Tang ¹
¹Department of Computer Science, National Tsing Hua University, Taiwan, ROC.
²Department 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