| |
| |
| Preface | |
| |
| |
| Acknowledgments | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| A Minimalist Introduction to Molecular Evolution | |
| |
| |
| |
| Birth of the Combinatorics of Genome Rearrangements | |
| |
| |
| |
| Statement of the Problem | |
| |
| |
| |
| Scope of This Survey | |
| |
| |
| |
| Overview of the Models | |
| |
| |
| |
| Organization of the Book | |
| |
| |
| |
| Duplication-Free Models: Permutations | |
| |
| |
| |
| Genomes as Permutations | |
| |
| |
| |
| The Symmetric Group | |
| |
| |
| |
| The Cycles of a Permutation | |
| |
| |
| |
| Signed Permutations | |
| |
| |
| |
| Distances on Permutation Groups | |
| |
| |
| |
| Circular Permutations | |
| |
| |
| |
| First Measures of Similarity between Permutations | |
| |
| |
| |
| Distances between Unsigned Permutations | |
| |
| |
| |
| Transposition Distance | |
| |
| |
| |
| Prefix Transposition Distance | |
| |
| |
| |
| Reversal Distance | |
| |
| |
| |
| Prefix Reversal Distance (Pancake-Flipping) | |
| |
| |
| |
| Variants | |
| |
| |
| |
| Relations between Distances on Unsigned Permutations | |
| |
| |
| |
| Distances between Signed Permutations | |
| |
| |
| |
| Conserved Interval Distance | |
| |
| |
| |
| Signed Reversal Distance | |
| |
| |
| |
| Variants of Sorting by Reversals | |
| |
| |
| |
| Combined Operations | |
| |
| |
| |
| Double Cut-and-Joins | |
| |
| |
| |
| Rearrangements of Partial Orders | |
| |
| |
| |
| Genomes as Partially Ordered Sets | |
| |
| |
| |
| Partially Ordered Sets | |
| |
| |
| |
| Constructing a Poset | |
| |
| |
| |
| Reversal Distance | |
| |
| |
| |
| Breakpoint Distance | |
| |
| |
| |
| Graph-Theoretic and Linear Algebra Formulations | |
| |
| |
| |
| Simple Permutations and the Interleaving Graph | |
| |
| |
| |
| The Overlap Graph | |
| |
| |
| |
| The Local Complementation of a Graph | |
| |
| |
| |
| The Matrix Tightness Problem | |
| |
| |
| |
| Extension to Sorting by Transpositions | |
| |
| |
| |
| The Intermediate Case of Directed Local Complementation | |
| |
| |
| |
| Models Handling Duplications: Strings | |
| |
| |
| |
| Generalities | |
| |
| |
| |
| Biological Motivations | |
| |
| |
| |
| Strings and Rearrangements on Strings | |
| |
| |
| |
| Balanced Strings | |
| |
| |
| |
| How to Deal with Multiple Copies? | |
| |
| |
| |
| Distances between Arbitrary Strings | |
| |
| |
| |
| The Match-and-Prune Model | |
| |
| |
| |
| The Block Edit Model | |
| |
| |
| |
| Distances between Balanced Strings | |
| |
| |
| |
| Minimum Common String Partition Problems | |
| |
| |
| |
| Reversal Distance | |
| |
| |
| |
| Unsigned Transpositions | |
| |
| |
| |
| Unsigned Block Interchanges | |
| |
| |
| |
| Relations between Distances | |
| |
| |
| |
| Multichromosomal Models | |
| |
| |
| |
| Paths and Cycles | |
| |
| |
| |
| Genomes | |
| |
| |
| |
| Breakpoints | |
| |
| |
| |
| Intervals | |
| |
| |
| |
| Translocation Distance | |
| |
| |
| |
| Double Cut-and-Joins (2-Break Rearrangement) | |
| |
| |
| |
| k-Break Rearrangement | |
| |
| |
| |
| Fusions, Fissions, Translocations, and Reversals | |
| |
| |
| |
| Rearrangements with Partially Ordered Chromosomes | |
| |
| |
| |
| Cycles of a Permutation | |
| |
| |
| |
| A Model for Multichromosomal Circular Genomes | |
| |
| |
| |
| A Generalization to Signed Genomes | |
| |
| |
| |
| Set Systems and the Syntenic Distance | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Structural Properties | |
| |
| |
| |
| Lower Bounds | |
| |
| |
| |
| Diameter | |
| |
| |
| |
| Algorithmic Results | |
| |
| |
| |
| Conjectures and Open Problems | |
| |
| |
| |
| Multigenomic Models | |
| |
| |
| |
| Median and Halving Problems | |
| |
| |
| |
| Breakpoint Median | |
| |
| |
| |
| Reversal and DCJ Median | |
| |
| |
| |
| Duplicated Genomes | |
| |
| |
| |
| Other Variants, Generalizations, and Discussion | |
| |
| |
| |
| Rearrangement Phylogenies | |
| |
| |
| |
| The Large Parsimony Problem | |
| |
| |
| |
| The Large Parsimony Problem with Gene Orders | |
| |
| |
| |
| Heuristics for the Breakpoint/Reversal Phylogeny Problem | |
| |
| |
| |
| Variants | |
| |
| |
| |
| Miscellaneous | |
| |
| |
| |
| Software | |
| |
| |
| |
| Pairwise Rearrangements | |
| |
| |
| |
| Phylogeny Reconstruction and Medians | |
| |
| |
| |
| Open Problems | |
| |
| |
| |
| Complexity Issues | |
| |
| |
| |
| Diameter | |
| |
| |
| |
| Tightness of Bounds | |
| |
| |
| Appendices | |
| |
| |
| |
| Graph Theory | |
| |
| |
| |
| Undirected Graphs | |
| |
| |
| |
| Directed Graphs | |
| |
| |
| |
| Complexity Theory | |
| |
| |
| |
| The Class NP | |
| |
| |
| |
| Some NP-Complete Problems | |
| |
| |
| Glossary | |
| |
| |
| Bibliography | |
| |
| |
| Index | |