SPRING

SPRING: Sorting Permutation by Reversals and block-INterchanGes

Input landmark-order data:

S1	son
	-206 -240 -136 -169 32 65 -60 -59 -41 -27 243 239 95 197 105 148 140 147 149 171 172 186 181 52 184 142 143 159 141 193 158 177 153 164 191 151 160 144 188 182 145 155 179 165 152 198 187 185 178 170 154 8 138 211 242 -61 -128 -214 1 2 -120 106 89 69 68 91 90 -234 109 84 31 30 23 -139 -71 -79 -224 117 227 62 48 67 93 208 103 75 124 213 189 112 -173 -195 -18 222 217 80 77 78 134 40 190 131 209 156 -107 -201 -232 63 -36 -24 -86 176 216 123 45 219 35 29 87 56 21 -44 19 20 82 22 203 204 34 4 110 111 161 -244 -127 -125 -126 -205 -215 200 -37 -175 -199 -64 -9 25 121 102 -33 57 -229 -72 -207 88 74 210 119 -225 137 -3 -39 -167 -132 135 -228 -81 -43 -212 -223 -58 115 -231 -230 -70 -53 241 235 220 -5 -233 -38 -122 -104 -130 -129 -85 -83 -73 -101 194 108 -133 76 6 -42 -236 -162 -157 -218 -66 -114 226 116 -28 -146 -192 -180 -118 -183 -150 -94 -202 -166 7 -196 -51 -46 -96 -100 -49 -97 -92 -99 -98 -47 -221 -168 -163 -26 -174 -50 238 -237 -113 -55 -12 -13 -16 -10 -17 -15 -14 -11 -54
S2	wgl
	54 11 14 15 17 10 16 13 12 55 -206 -240 -136 -169 32 65 76 6 -42 -23 186 181 52 -57 33 -238 50 174 222 -235 110 111 -135 132 167 39 3 207 72 225 -119 -210 -63 232 201 9 -58 161 7 -101 121 -231 -183 -150 -36 -82 -20 -19 -241 79 71 -118 89 69 68 77 78 134 -196 -51 -46 -96 -100 -49 -97 -92 -99 -98 -47 -221 -112 -189 -213 -124 -75 -103 -93 -67 -48 -62 -5 18 74 44 -21 40 131 190 209 156 223 -113 -90 -91 -146 -192 -180 126 125 127 26 -208 166 25 -218 205 37 56 -85 -83 -73 194 -30 -31 -237 -128 -214 109 212 43 80 -2 -1 94 -22 228 -137 217 -102 -66 -114 226 116 117 227 -38 -122 229 -29 -219 -45 -123 -35 -216 -176 86 24 -87 163 168 -61 -204 -203 106 -81 -234 84 64 -224 -242 107 220 129 130 104 -173 -195 -236 -162 -157 -244 -175 -199 -200 215 -41 -27 243 28 202 -139 -120 95 197 105 148 140 147 149 171 172 34 4 -233 133 -88 -239 184 142 143 159 141 193 158 177 153 164 191 151 160 144 188 182 145 155 179 165 152 198 187 185 178 170 154 53 70 8 138 211 59 60 115 108 -230

Rearrangement Events: Reversal with weight 1 and Block-interchange with weight 2

Chromosomal type: circular

Computed breakpoint distance matrix and the corresponding phylogenetic tree:

	S1	S2
S1	-	113
S2	113	-

Computed rearrangement distance matrix and the corresponding phylogenetic tree:

	S1	S2
S1	-	109
S2	109	-

Optimal scenario of weighted reversals and block-interchanges:
The minimum cost of series for transforming S2 into S1 is 109 which is composed of 105 reversals and 2 block-interchanges.

(54 11 14 15 17 10 16 13 12 55 -206 -240 -136 -169 32 65 76 6 -42 -23 186 181 52 -57 33 -238 50 174 222 -235 110 111 -135 132 167 39 3 207 72 225 -119 -210 -63 232 201 9 -58 161 7 -101 121 -231 -183 -150 -36 -82 -20 -19 -241 79 71 -118 89 69 68 77 78 134 -196 -51 -46 -96 -100 -49 -97 -92 -99 -98 -47 -221 -112 -189 -213 -124 -75 -103 -93 -67 -48 -62 -5 18 74 44 -21 40 131 190 209 156 223 -113 -90 -91 -146 -192 -180 126 125 127 26 -208 166 25 -218 205 37 56 -85 -83 -73 194 -30 -31 -237 -128 -214 109 212 43 80 -2 -1 94 -22 228 -137 217 -102 -66 -114 226 116 117 227 -38 -122 229 -29 -219 -45 -123 -35 -216 -176 86 24 -87 163 168 -61 -204 -203 106 -81 -234 84 64 -224 -242 107 220 129 130 104 -173 -195 -236 -162 -157 -244 -175 -199 -200 215 -41 -27 243 28 202 -139 -120 95 197 105 148 140 147 149 171 172 34 4 -233 133 -88 -239 184 142 143 159 141 193 158 177 153 164 191 151 160 144 188 182 145 155 179 165 152 198 187 185 178 170 154 53 70 8 138 211 59 60 115 108 -230)

(-206 -240 -136 -169 32 65 -60 -59 -41 -27 243 239 95 197 105 148 140 147 149 171 172 186 181 52 184 142 143 159 141 193 158 177 153 164 191 151 160 144 188 182 145 155 179 165 152 198 187 185 178 170 154 8 138 211 242 -61 -128 -214 1 2 -120 106 89 69 68 91 90 -234 109 84 31 30 23 -139 -71 -79 -224 117 227 62 48 67 93 208 103 75 124 213 189 112 -173 -195 -18 222 217 80 77 78 134 40 190 131 209 156 -107 -201 -232 63 -36 -24 -86 176 216 123 45 219 35 29 87 56 21 -44 19 20 82 22 203 204 34 4 110 111 161 -244 -127 -125 -126 -205 -215 200 -37 -175 -199 -64 -9 25 121 102 -33 57 -229 -72 -207 88 74 210 119 -225 137 -3 -39 -167 -132 135 -228 -81 -43 -212 -223 -58 115 -231 -230 -70 -53 241 235 220 -5 -233 -38 -122 -104 -130 -129 -85 -83 -73 -101 194 108 -133 76 6 -42 -236 -162 -157 -218 -66 -114 226 116 -28 -146 -192 -180 -118 -183 -150 -94 -202 -166 7 -196 -51 -46 -96 -100 -49 -97 -92 -99 -98 -47 -221 -168 -163 -26 -174 -50 238 -237 -113 -55 -12 -13 -16 -10 -17 -15 -14 -11 -54)

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