1 |
Introduction |
1.1 |
A Minimalist Introduction to Molecular Evolution |
1 |
|
|
|
1.2 |
Birth of the Combinatorics of Genome Rearrangements |
4 |
|
|
|
1.3 |
Statement of the Problem |
6 |
|
|
|
1.4 |
Scope of This Survey |
7 |
|
|
|
1.5 |
Overview of the Models |
7 |
|
|
|
1.6 |
Organization of the Book |
8 |
|
I |
DUPLICATION-FREE MODELS: PERMUTATIONS |
11 |
|
2 |
Genomes as Permutations |
13 |
|
|
|
2.1 |
The Symmetric Group |
13 |
|
|
|
2.2 |
The Cycles of a Permutation |
14 |
|
|
|
2.3 |
Signed Permutations |
15 |
|
|
|
2.4 |
Distances on Permutation Groups |
15 |
|
|
|
2.5 |
Circular Permutations |
18 |
|
|
|
2.6 |
First Measures of Similarity between Permutations |
20 |
|
3 |
Distances between Unsigned Permutations |
25 |
|
|
|
3.1 |
Transposition Distance |
25 |
|
|
|
3.2 |
Prefix Transposition Distance |
36 |
|
|
|
3.3 |
Reversal Distance |
40 |
|
|
|
3.4 |
Prefix Reversal Distance (Pancake-Flipping) |
47 |
|
|
|
3.5 |
Variants |
49 |
|
|
|
3.6 |
Relations between Distances on Unsigned Permutations |
61 |
|
4 |
Distances between Signed Permutations |
63 |
|
|
|
4.1 |
Conserved Interval Distance |
63 |
|
|
|
4.2 |
Signed Reversal Distance |
64 |
|
|
|
4.3 |
Variants of Sorting by Reversals |
69 |
|
|
|
4.4 |
Combined Operations |
72 |
|
|
|
4.5 |
Double Cut-and-Joins |
73 |
|
5 |
Rearrangements of Partial Orders |
75 |
|
|
|
5.1 |
Genomes as Partially Ordered Sets |
75 |
|
|
|
5.2 |
Partially Ordered Sets |
75 |
|
|
|
5.3 |
Constructing a Poset |
78 |
|
|
|
5.4 |
Reversal Distance |
79 |
|
|
|
5.5 |
Breakpoint Distance |
80 |
|
6 |
Graph-Theoretic and Linear Algebra Formulations |
83 |
|
|
|
6.1 |
Simple Permutations and the Interleaving Graph |
83 |
|
|
|
6.2 |
The Overlap Graph |
84 |
|
|
|
6.3 |
The Local Complementation of a Graph |
85 |
|
|
|
6.4 |
The Matrix Tightness Problem |
85 |
|
|
|
6.5 |
Extension to Sorting by Transpositions |
86 |
|
|
|
6.6 |
The Intermediate Case of Directed Local Complementation |
87 |
|
II |
MODELS HANDLING DUPLICATIONS: STRINGS |
89 |
|
7 |
Generalities |
91 |
|
|
|
7.1 |
Biological Motivations |
91 |
|
|
|
7.2 |
Strings and Rearrangements on Strings |
92 |
|
|
|
7.3 |
Balanced Strings |
94 |
|
|
|
7.4 |
How to Deal with Multiple Copies? |
95 |
|
8 |
Distances between Arbitrary Strings |
97 |
|
|
|
8.1 |
The Match-and-Prune Model |
98 |
|
|
|
8.2 |
The Block Edit Model |
123 |
|
9 |
Distances between Balanced Strings |
133 |
|
|
|
9.1 |
Minimum Common String Partition Problems |
133 |
|
|
|
9.2 |
Reversal Distance |
138 |
|
|
|
9.3 |
Unsigned Transpositions |
147 |
|
|
|
9.4 |
Unsigned Block Interchanges |
153 |
|
|
|
9.5 |
Relations between Distances |
157 |
|
III |
MULTICHROMOSOMAL MODELS |
159 |
|
10 |
Paths and Cycles |
161 |
|
|
|
10.1 |
Genomes |
161 |
|
|
|
10.2 |
Breakpoints |
162 |
|
|
|
10.3 |
Intervals |
163 |
|
|
|
10.4 |
Translocation Distance |
164 |
|
|
|
10.5 |
Double Cut-and-Joins (2-Break Rearrangement) |
170 |
|
|
|
10.6 |
k-Break Rearrangement |
171 |
|
|
|
10.7 |
Fusions, Fissions, Translocations, and Reversals |
172 |
|
|
|
10.8 |
Rearrangements with Partially Ordered Chromosomes |
174 |
|
11 |
Cycles of a Permutation |
175 |
|
|
|
11.1 |
A Model for Multichromosomal Circular Genomes |
175 |
|
|
|
11.2 |
A Generalization to Signed Genomes |
178 |
|
12 |
Set Systems and the Syntenic Distance |
181 |
|
|
|
12.1 |
Introduction |
181 |
|
|
|
12.2 |
Structural Properties |
182 |
|
|
|
12.3 |
Lower Bounds |
184 |
|
|
|
12.4 |
Diameter |
185 |
|
|
|
12.5 |
Algorithmic Results |
185 |
|
|
|
12.6 |
Conjectures and Open Problems |
189 |
|
IV |
MULTIGENOMIC MODELS |
191 |
|
13 |
Median and Halving Problems |
193 |
|
|
|
13.1 |
Breakpoint Median |
194 |
|
|
|
13.2 |
Reversal and DCJ Median |
197 |
|
|
|
13.3 |
Duplicated Genomes |
199 |
|
|
|
13.4 |
Other Variants, Generalizations, and Discussion |
205 |
|
14 |
Rearrangement Phylogenies |
207 |
|
|
|
14.1 |
The Large Parsimony Problem |
207 |
|
|
|
14.2 |
The Large Parsimony Problem with Gene Orders |
209 |
|
|
|
14.3 |
Heuristics for the Breakpoint/Reversal Phylogeny Problem |
211 |
|
|
|
14.4 |
Variants |
220 |
|
V |
MISCELLANEOUS |
221 |
|
15 |
Software |
223 |
|
|
|
15.1 |
Pairwise Rearrangements |
223 |
|
|
|
15.2 |
Phylogeny Reconstruction and Medians |
226 |
|
16 |
Open Problems |
229 |
|
|
|
16.1 |
Complexity Issues |
229 |
|
|
|
16.2 |
Diameter |
231 |
|
|
|
16.3 |
Tightness of Bounds |
232 |
|
|
APPENDICES |
233 |
|
A |
Graph Theory |
235 |
|
|
|
A.1 |
Undirected Graphs |
235 |
|
|
|
A.2 |
Directed Graphs |
240 |
|
B |
Complexity Theory |
243 |
|
|
|
B.1 |
The Class NP |
243 |
|
|
|
B.2 |
Some NP-Complete Problems |
252 |
|
|
Glossary |
257 |
|
|
Bibliography |
263 |
|
|
Index |