Content

•  
  1 Introduction
•  
   1.1 Introduction to Genomes
•  
   1.1.1 Organisation of Genetic Information
•  
   1.1.2 Genome Nomenclature
•  
   1.2 Comparative Genomics
•  
   1.2.1 Genome Modifications
•  
   1.2.2 Genome Modification Models
•  
   1.3 Content and Structure of the Thesis
•  
  2 Important Data Structures and Models
•  
   2.1 Insertions and Deletions
•  
   2.1.1 Core Genomes and Unique Markers
•  
   2.1.2 A First Upper Bound to the Distance with Unique Markers
•  
   2.1.3 Extremities, Adjacencies and Labels
•  
   2.1.4 The Indel Operation on G-Adjacencies
•  
  2.2 Graph Structures for Representing Genomic Relations
•  
   2.2.1 Breakpoint Graph
•  
   2.2.2 Adjacency Graph
•  
   2.2.3 Master Graph
•  
   2.2.4 Properties of Cycles
•  
   2.2.5 A Note on Relations between the Types of Graphs
•  
  2.3 The Double Cut-and-Join Model
•  
   2.3.1 The DCJ Operation on Unlabelled G-Adjacencies
•  
   2.3.2 The Effect of a DCJ Operation on the Adjacency Graph
•  
   2.3.3 Distance and Sorting
•  
   3 Uniform Sampling of DCJ Sorting Scenarios
•  
  3.1 Sampling by Sorting Components Individually
•  
   3.1.1 Solution Space for DCJ Sorting without Recombinations
•  
   3.1.2 Bundling Cases with Identical Distance Values
•  
   3.1.3 Bundling Cases with Identical Change(s) in Distance Value
•  
   3.1.4 Sampling Weights for a Distance-Splitgroup-Pair
•  
   3.1.5 Uniform Sampling of an Optimal DCJ Operation
•  
   3.2 Implementation into UniMoG
•  
   3.2.1 Drawing a Huge Random Integer
•  
   3.2.2 Example Output
•  
  3.3 Evaluation
•  
   3.3.1 Overview of Sampling Methods
•  
   3.3.2 Real Data
•  
   3.3.3 Artificial Data
•  
   3.4 Discussion
•  
   4 DCJ-indel Model on Circular Genomes Via DCJ Distance
•  
   4.1 Generalising the DCJ Model and Distance
•  
   4.1.1 The DCJ Operation on Labelled G-Adjacencies
•  
   4.2 DCJ and indel Operations on a Labelled Cycle
•  
   4.3 DCJ Operations on a Pair of Labelled Cycles
•  
   4.4 Distance
•  
  4.5 On Sorting With Indels
•  
   4.5.1 Introducing Insertions from a B-run
•  
   4.5.2 Optimal Completion
•  
   5 Inversion-indel Distance Problems
•  
   5.1 Distance Relations
•  
   5.2 Preliminaries
•  
   5.2.1 Effect of an Inversion on Cycles
•  
   5.2.2 Component Groups
•  
   5.2.3 Component Group Relations
•  
   5.2.4 Effect of an Inversion on Component Groups
•  
   5.3 Resolving Unlabelled Good Components
•  
   5.4 Resolving Labelled Good Components
•  
   5.4.1 Finding Safe Integrations
•  
   5.4.2 The Inversion-indel Distance on Good Components
•  
   5.5 Handling AB-Cycles and AB-Component Groups
•  
   5.6 The Labelled Component Group Tree
•  
   5.6.1 Resolving Bad Unlabelled Component Groups
•  
   5.6.2 The Bad Component Group Tree To
•  
   5.7 Chapter Summary
•  
   6 Optimal Tree Covers of To
•  
   6.1 Covering Paths and Tree Covers
•  
   6.1.1 Cost of a Cover Bounded by Individual Subtrees
•  
   6.2 Properties of To Influencing the Cost of Optimal Covers
•  
   6.2.1 Separation Types
•  
   6.2.2 Links of Subtrees
•  
   6.2.3 Short Paths
•  
   6.2.4 Property Set of To
•  
   6.3 Heterogeneous Paths
•  
   6.4 The Residual Tree Tr
•  
   6.4.1 Residual Trees With One Type of Leaf Labelling
•  
   6.4.2 Residual Trees With Two Types of Leaf Labelling
•  
   6.4.3 Residual Trees With Three Types of Leaf Labelling
•  
   6.4.4 Residual Trees With Four Types of Leaf Labelling
•  
   6.4.5 Strategy for Reduction in the General Case
•  
   6.5 Chapter Summary
•  
  7 Inversion-indel Distance and Sorting
•  
   7.1 The General Inversion-indel Distance
•  
  7.2 Sorting with Inversions, Insertions and Deletions
•  
   7.2.1 The Residual Tree Cover as Precursor
•  
   7.2.2 Sorting with Inversions and Deletions
•  
  7.3 Model Limitations and Extensions
•  
   7.3.1 Multichromosomal Genomes
•  
   7.3.2 Co-tailed Genomes
•  
  8 Final Remarks
•  
   8.1 Summary
•  
   8.2 Prospects
•  
   Bibliography
•  
   Notations
•  
  Appendix
•  
  A Additional Examples
•  
   A.1 Unsafe Covering Paths
•  
   A.2 Non-Separated Labelled Tree
•  
   A.3 Separations
•  
   A.4 Short and Long e-Branches
•  
   A.5 Counter-Example for Reduction of AB-Leaves
•  
   A.6 The Number of Separating Vertices Matters
•  
   B Bounds to an Optimal Tree Cover With Restraints
•  
  C Cover Descriptions
•  
   C.1 Nomenclature
•  
   C.2 Trees with Two Leaf Types
•  
   C.3 Trees with Three Leaf Types
•  
   C.4 Trees with Four Leaf Types
•  
   D Detailed Sampling Results for sty-stm Comparison of Y-Proteobacteria