Key Information
About the content
If you look at two genes that serve the same purpose in two different species, how can you rigorously compare these genes in order to see how they have evolved away from each other?
In the first part of the course, part of the Algorithms and Data Structures MicroMasters program, we will see how the dynamic programming paradigm can be used to solve a variety of different questions related to pairwise and multiple string comparison in order to discover evolutionary histories.
In the second part of the course, we will see how a powerful machine learning approach, using a Hidden Markov Model, can dig deeper and find relationships between less obviously related sequences, such as areas of the rapidly mutating HIV genome.
- Dynamic programming and how it applies to basic string comparison algorithms
- Sequence alignment, including how to generalize dynamic programming algorithms to handle different cases
- Hidden markov models
- How to find the most likely sequence of events given a collection of outcomes and limited information
- Machine learning in sequence alignment
Prerequisite
Basic knowledge of:
- at least one programming language: loops, arrays, stacks, recursion.
- mathematics: proof by induction, proof by contradiction.
Syllabus
Week 1: Pairwise Sequence Alignment
A review of dynamic programming, and applying it to basic string comparison algorithms.
Week 2: Advanced Sequence Alignment
Learn how to generalize your dynamic programming algorithm to handle a number of different cases, including the alignment of multiple strings.
Week 3: Introduction to Hidden Markov Models
Learn what a Hidden Markov model is and how to find the most likely sequence of events given a collection of outcomes and limited information.
Week 4: Machine Learning in Sequence Alignment
Formulate sequence alignment using a Hidden Markov model, and then generalize this model in order to obtain even more accurate alignments.
Instructors
Pavel Pevzner
Ronald R. Taylor Professor of Computer Science
The University of California, San Diego
Phillip Compeau
Assistant Teaching Professor
Carnegie Mellon University
Content Designer
Platform
Harvard University, the Massachusetts Institute of Technology, and the University of California, Berkeley, are just some of the schools that you have at your fingertips with EdX. Through massive open online courses (MOOCs) from the world's best universities, you can develop your knowledge in literature, math, history, food and nutrition, and more. These online classes are taught by highly-regarded experts in the field. If you take a class on computer science through Harvard, you may be taught by David J. Malan, a senior lecturer on computer science at Harvard University for the School of Engineering and Applied Sciences. But there's not just one professor - you have access to the entire teaching staff, allowing you to receive feedback on assignments straight from the experts. Pursue a Verified Certificate to document your achievements and use your coursework for job and school applications, promotions, and more. EdX also works with top universities to conduct research, allowing them to learn more about learning. Using their findings, edX is able to provide students with the best and most effective courses, constantly enhancing the student experience.
