Inhalt

•  
   1 Introduction
•  
   1.1 Modeling Gene Order
•  
   1.1.1 Homology Assignment
•  
   1.1.2 Basic Models
•  
   1.1.3 Model Variants
•  
   1.2 Comparative Genomics
•  
   1.3 Phylogeny
•  
   1.4 Overview of the Thesis
•  
   1.5 Acknowledgements
•  
   2 Labeling a Phylogenetic Tree with Sets of Gene Clusters
•  
   2.1 Abstract Gene Cluster Model
•  
  2.2 Labelings and Their Properties
•  
   2.2.1 Consistency
•  
   2.2.2 Parsimony
•  
   2.3 The Labeling Problem
•  
   3 An Algorithmical Framework to Find an Optimal Labeling
•  
   3.1 Fitch and Hartigan
•  
   3.2 Finding Conflicts
•  
   3.2.1 Practical Enhancements
•  
   3.3 Branch-And-Bound Search
•  
   3.4 Two-Phase Approach
•  
   3.5 Complexity
•  
   4 Permutation-based Gene Cluster Models
•  
   4.1 Adjacencies on Permutations
•  
   4.1.1 Efficient Filtering
•  
   4.1.2 Model Variants
•  
   4.2 Common Intervals on Permutations
•  
   4.2.1 Efficient Filtering with PQ Trees
•  
   4.2.2 Generalized Models
•  
   4.3 Framed Common Intervals on Permutations
•  
   4.4 Nested Common Intervals on Permutations
•  
   4.4.1 Modified Preprocessing
•  
  4.5 Evaluation on Simulated Data
•  
   4.5.1 Simulation Setup
•  
   4.5.2 Results
•  
   5 Sequence-based Gene Cluster Models
•  
  5.1 Consistency on Sequences
•  
   5.1.1 Restricting the Multiplicity of Genes
•  
   5.1.2 Sequences without Duplications
•  
   5.2 Adjacencies on Sequences
•  
   5.2.1 The Gene Order Graph
•  
   5.2.2 Evaluation on Simulated Data
•  
   5.3 Common Intervals on Sequences
•  
   5.4 Variants of Common Intervals on Sequences
•  
   6 The Evolution of the Corynebacterium Genome
•  
  6.1 Data Preparation and General Results
•  
   6.1.1 Homology Assignment and Further Preprocessing
•  
   6.1.2 Reconstruction Results
•  
   6.2 Cell Wall Biosynthesis Block
•  
   6.3 Central Metabolism
•  
   6.4 DNA Synthesis
•  
   7 Conclusion and Outlook
•  
    Bibliography
•  
   A NP-Completeness Proofs
•  
   A.1 The 3-Bipartite Hamiltonian Cycle Problem
•  
   A.2 Consistency Problem for Common Intervals on Sequences
•  
   A.3 Consistency Problem for Framed Common Intervals on Sequences
•  
   A.4 Consistency Problem for Nested Common Intervals on Sequences