課程大綱： 字符串處理和模式匹配算法培訓
Weeks 1 and 2: Suffix Trees How would you search for a longest repeat
in a string in LINEAR time? In 1973, Peter Weiner came up with a surprising solution that was based on suffix trees,
the key data structure in pattern matching.
Computer scientists were so impressed with his algorithm that they called
it the Algorithm of the Year. In this lesson, we will explore some key ideas
for pattern matching that will - through a series of trials and errors - bring us to suffix trees.
Week 3 and 4: Burrows-Wheeler Transform and Suffix Arrays Although EXACT pattern matching with suffix trees is fast,
it is not clear how to use suffix trees for APPROXIMATE pattern matching.
In 1994, Michael Burrows and David Wheeler invented an ingenious algorithm for text compression
that is now known as Burrows-Wheeler Transform.
They knew nothing about genomics,
and they could not have imagined that 15 years later their algorithm will become
the workhorse of biologists searching for genomic mutations.
But what text compression has to do with pattern matching???
In this lesson you will learn that the fate of an algorithm is often hard to predict – its applications may appear
in a field that has nothing to do with the original plan of its inventors.
加入高級會員獲得助教答疑
