Inhalt

•  
   1 Introduction
•  
  2 Background
•  
   2.1 Genetic information
•  
   2.2 Evolutionary modifications
•  
   2.3 Evolutionary relationships
•  
  2.4 Genome model
•  
   2.4.1 Genomes, chromosomes, and genes
•  
   2.4.2 Telomeres
•  
   2.5 The Family-free Principle
•  
  3 Family-free adjacencies
•  
   3.1 Breakpoint distance
•  
   3.2 Pairwise family-free adjacencies
•  
   3.3 Family-free adjacencies for more than two genomes
•  
   3.4 Computational complexity of pairwise family-free adjacencies
•  
   3.4.1 Reduction from exemplar breakpoint distance problem
•  
   3.4.2 Maximum matchings in solutions to problem FF-Adjacencies
•  
   3.5 Bounds
•  
   3.6 An exact solution to problem FF-Adjacencies
•  
   3.7 Speeding up computations
•  
   3.7.1 Identifying anchors in the gene similarity graph
•  
   3.7.2 Remaining subgraph test
•  
   3.8 A heuristic solution to problem FF-Adjacencies
•  
   3.9 Experimental results and discussion
•  
   3.9.1 Simulated genome evolution
•  
   3.9.2 Runtime
•  
   3.9.3 Quality of orthology assignments
•  
   3.9.4 Experimental results on a biological dataset
•  
   3.9.5 Discussion
•  
  4 Family-free median
•  
   4.1 Gene family-based median of three
•  
   4.2 A family-free generalization
•  
   4.3 Complexity of problem FF-Median
•  
   4.3.1 Reduction
•  
   4.4 An exact solution to problem FF-Median
•  
   4.5 The effect of gene family evolution on family-free medians
•  
   4.6 Solving problem FF-Adjacencies for three genomes
•  
   4.7.1 Simulations
•  
   4.7.2 Experiments on a biological dataset
•  
   4.7.3 Discussion
•  
  5 Family-free synteny
•  
   5.1 Generalized adjacencies
•  
   5.2 Synteny and gene clusters
•  
  5.3 Family-free syntenic blocks
•  
   5.3.1 A naïve approach
•  
   5.3.2 A practical approach
•  
   5.4 Common intervals in indeterminate strings
•  
   5.5 Discovering weak common intervals
•  
   5.5.1 Updating table Int
•  
   5.5.2 Computing table Succ
•  
   5.6 Discovering strict common intervals
•  
   5.7 Discovering approximate weak common intervals
•  
   5.8 A runtime heuristic for discovering approx. weak common intervals
•  
  5.9 Results and Discussion
•  
   5.9.1 Gene family-based dataset
•  
   5.9.2 Gene family-free dataset
•  
   5.9.3 Comparison with RegulonDB
•  
   5.9.4 Discussion
•  
   6 Conclusion and outlook
•  
   Bibliography