CS 482 | SCS | UW

Revised July 3, 2015

CS 482: Computational Techniques in Biological Sequence Analysis

General description

This course introduces the most well known bioinformatics problems and the algorithms behind their solutions. These problems include sequence alignment, large-scale sequence database search, evolutionary tree reconstruction, gene prediction, and protein sequencing. Students explore the underlying computational techniques and skills to solve similar problems.

Logistics

Audience

  • Students taking the Bioinformatics option or students interested in learning how to apply mathematical modeling and algorithmic methods to solve biological problems. Usually taken in fourth year.

Normally available

  • Winter

Related courses

  • Pre-requisites: CS 341, STAT 241 or at least 60% in STAT 231

For official details, see the UW calendar.

Software/hardware used

  • A personal computer for programming

Typical reference(s)

  • R. Durbin, S. Eddy, A. Krogh and G. Mitchison, Biological Sequence Analysis, Cambridge Press, 1999

Required preparation

At the start of the course, students should be able to

  • Program in Java, C++, or Python
  • Design algorithms and analyze an algorithm's complexity
  • Describe basic concepts in molecular biology or quickly learn the concepts in the first few weeks

Learning objectives

At the end of the course, students should be able to

  • Find and use common bioinformatics resources and tools
  • Apply the learned modeling and algorithmic techniques to solve computational problems in biology
  • Apply the learned modeling and algorithmic techniques to solve data analysis problems in other areas

Typical syllabus

Introduction

  • Brief review of the fundamentals of molecular biology and genetics in the context of biology as an information science.

Pairwise sequence alignment

  • Classic dynamic programming ideas for pairwise sequence alignment
  • Statistical measures of alignment significance
  • Probabilistic models of homologous sequences

Heuristic sequence alignment

  • Mathematical ideas underlying BLAST, FASTA and other heuristic sequence aligners
  • Applications of sequence alignment
  • Multiple alignment

Exact string matching

  • Suffix trees, suffix arrays, and their application in pairwise and multiple alignment

Sequence annotation

  • Gene finding
  • Sequence feature detection
  • Motif finding
  • Hidden Markov models

Evolutionary tree algorithms

  • Classical and contemporary algorithms for inferring evolutionary trees

Protein sequence identification

  • Mass spectrometry and its application in protein identification and sequencing