Contents

• List of Figures
• List of Tables
• Introduction and Motivation
  • Genome and EST sequencing projects
  • State of the art assembly
  • Aim of the thesis
  
  
• Fundamentals of sequencing and assembly - integrating biology and computer science
  • Definitions and methods
  • Error types and rates in DNA sequencing
    • Errors of the data acquisition process
    • Errors due to biology
  • Peculiarities of sequencing expressed sequence tags (ESTs)
    • Biological background
    • Implications for assembly projects
      • Abundance of mRNA transcripts
      • Splice variants
  
  
• Assembly strategies
  • Short overview of existing strategies
  • Developing a new strategy
    • Tackling misassemblies
    • Focussing on observable data
    • Pattern analysis
  
  
• Methods and Algorithms
  • Data preprocessing and input
  • Read scanning
    • Formalising the problem
    • Present algorithms
    • DNA-Shift-AND algorithm
    • The ZEBRA algorithm
  • Systematic match inspection
    • Improving Smith-Waterman alignment by banding
    • Parametrising Smith-Waterman alignment
    • Attributing an alignment overlap
    • Building a graph
  • Building contigs
    • Pathfinder and contig interaction
    • Path traversal strategies
      • Simple greedy algorithm
      • n, m-step recursive look-ahead strategy
    • Contig
    • Contig approval methods
      • Acceptance upon actual consensus constraints
      • Repeat marker tags
      • Simple signal analysis
      • Template size constraints
    • Consensus and consensus quality computation
  • Automatic editing
  • Finding previously unknown repeats
    • Repeat types
    • Existing approaches
    • Locating repeats through error pattern analysis
  • Read extension
    • Intra-contig and extra-contig read extension
    • Extension algorithms
  • Iterative cycling
  • Modifications for EST assembly and SNP detection
    • Coverage: meeting both extremes
    • Detection of SNPs in genes and gene families
    • Classification of SNPs
  
  
• Results and discussion
  • Genome assembly
  • EST assembly
  • Discussion
  
  
• Conclusion and outlook
• Development details
  • Programming environment
  • Programming approaches
  • Code statistics
  
  
• Manual pages
• Bibliography
• Index
• Acknowledgements