June 17th, 2005


BLAST and dynamic programming r 2 1337

As those of you who have been following the story of my course, CIS 690, Data Mining in Bioinformatics, may recall, I have changed the prerequisite from CIS 300 (Data Structures and Algorithms) to CIS 200 (Introduction to Computer Science).

There are 10 people in the class but only 5 are taking it: 3 CIS undergrads, 1 Ph.D. student in Math, and 1 Ph.D. student in Statistics. That leaves 5 auditors: 1 M.S. student in CIS (and Ph.D. student in Stats), 1 Ph.D. student in CIS, 1 statistics faculty member, and 2 SUROP students (Math and CS).

"How does one cater to such a diverse audience?" I wondered. A couple of them are quite familiar with BLAST and dynamic programming, while the whole concept of string matching algorithms (or algorithms in general) is new to others.

Thus did I come up with the following example for explaining edit distance and k-approximate string matching today:

--u-r- 2-- q--l 4-- mee!1!!
++|+|+ x++ x++| x++ ||-|---    insert (10) / delete (4) / twiddle (3)
you're too cool for me-!---

Collapse )