Bioinformatics lecture notes
  • Introduction
  • Introduction to biology (for computer scientists)
  • Ethical considerations
  • Finding patterns in DNA
    • Introduction to pattern discovery
    • Looking for frequent k-mers
    • Leveraging biology
    • Finding genes
  • Exact string matching
    • Introduction to exact string matching
    • Semi-numerical matching
    • The Z algorithm
    • The KMP algorithm
  • Multiple sequence alignment
    • Introduction to multiple sequence alignment
    • Motif finding
  • String indexing
    • Introduction to string indexing
    • Introduction to suffix trees
    • Suffix trees: beyond the basics
    • Suffix arrays
    • The Burrows-Wheeler transform and the FM-index
  • Inexact alignment
    • Introduction to inexact alignment
    • Inexact alignment calculation with dynamic programming
    • Example: filling the dynamic programming table
    • Modeling alignment as a graph
    • Backtracking through the dynamic programming table
    • From edit distance to alignment scores
    • Local alignment
    • Exercises
  • Advanced inexact alignment
    • Gap penalties
    • Sequence alignment in linear space
    • Sequence alignment with bounded error
  • Proteomics data analysis
    • Introduction to proteomic data analysis
    • From peptides to theoretical spectra
    • Cyclopeptide sequencing
    • Dealing with errors in experimental spectra
  • Data clustering
    • Introduction to data clustering
    • K-means clustering
    • Hierarchical clustering
  • Phylogenetic analysis
    • Introduction to phylogenetic inference
    • Distance-based phylogenetic analysis
    • Trait-based phylogenetic inference
  • Sequence assembly
    • Introduction to sequence assembly
    • Graph formulations of sequence assembly
    • Finding Eulerian tours
  • Gene finding and annotation
    • Introduction to sequence annotation
    • Gene finding
    • Introduction to Hidden Markov Models
    • Taxonomic and functional annotation
Powered by GitBook
On this page
  1. Inexact alignment

Exercises

  1. Describe a dynamic programming algorithm that solves the longest common subsequence problem—find the largest number of letters that occur in the same order in two strings. For example, the longest common subsequence of ABCDGH and AEDFHR is ADH:

    ABCDGH
A  D H
AE DFHR

  2. Describe a dynamic programming algorithm that solves a "global-local" (or "fitting") alignment: find the best alignment of a short string (query) inside a longer string (text), or more precisely the highest scoring alignment between a query string and a substring of a text string. Yet another way of saying it, the alignment must use the full query but can ignore characters at the beginning and end of the text. Describe how you would modify either the global or local alignment algorithm to solve this problem: How would you initialize the first row/column of the matrix? What recurrence equations would you use (local or global)? From which location in the matrix would you start the backtracking process?

  3. Describe a dynamic programming algorithm that solves an "overlap" alignment: the highest scoring alignment of the suffix of S1 to the prefix of S2. Describe how you would modify either the global or local alignment algorithm to solve this problem: How would you initialize the first row/column of the matrix? What recurrence equations would you use (local or global)? From which location in the matrix would you start the backtracking process?

  4. Describe a dynamic programming algorithm that solves a "suffix" alignment: the highest scoring alignment of the suffix of S1 to the suffix of S2.

    Describe how you would modify either the global or local alignment algorithm to solve this problem: How would you initialize the first row/column of the matrix? What recurrence equations would you use (local or global)? From which location in the matrix would you start the backtracking process?

  5. Describe a dynamic programming algorithm that solves a partial "prefix" alignment: the highest scoring alignment of a prefix of S1 to the entirety of S2. Describe how you would modify either the global or local alignment algorithm to solve this problem: How would you initialize the first row/column of the matrix? What recurrence equations would you use (local or global)? From which location in the matrix would you start the backtracking process?

  6. Describe a dynamic programming algorithm that solves a partial "suffix" alignment: the highest scoring alignment of a suffix of S1 to the entirety of S2. Describe how you would modify either the global or local alignment algorithm to solve this problem: How would you initialize the first row/column of the matrix? What recurrence equations would you use (local or global)? From which location in the matrix would you start the backtracking process?

PreviousLocal alignmentNextGap penalties

Last updated 4 months ago