CPSC 445 Bioinformatics Algorithms (2021)

About (and prerequisites)

CPSC 445 is a computer science algorithms course. Basic understanding of algorithm design and analysis is a requirement for this course. Basic understanding of genomics is helpful but NOT necessary for this course.

The course will cover computational methods that are used to process and deal with high-throughput genomic sequencing data. These methods include string search, sequence pattern matching, sequence alignment, and genome assembly.

Logistics

Instructor: Faraz Hach

Instructor email:

Webpage: https://www.cs.ubc.ca/~fhach/cpsc445

TA: A.Safa and P. Ye

Material

Quizzes will be based on required reading materials and the lectures.

• Required reading:

• Mostly from An Introduction to Bioinformatics Algorithms by N. C. Jones and P. A. Pevzner (Pvz)
• Occasionally from Introduction to Algorithms by CLRS

• Further readings:

• Genome-Scale Algorithm Design by MBCT

Grading policy (Tentative)

• Homework: 30%

• 5 assignments
• 6% each

• Quiz: 20%

• 10-12 quizzes

2% each (Best Ten)

• Midterm: 20%
• Final: 30%

The university’s policies on scholarly integrity and the department’s on collaboration and plagiarism are going to be followed in this course.

Syllabus topics

• Algorithmic complexity review
• Exact matching

• KMP - Boyer Moore
• Suffix Tree and Array
• Aho-Crosaik
• Suffix Array
• Burrows-Wheeler Transform and FM-index
• Rabin-Karp algorithm

• Alignment

• Global
• Local
• Affined Gap Models
• Multiple Sequence Alignment

• Motif finding problem
• Phylogentetics

• UPGMA
• Sankoff Algorithm
• Neighbor Joining
• Fitch Algorithm

• Hidden Markov Models
• Motis