CSC 570: Special Topics in Computer Science: Bioinformatics
Fall 2011

Instructor: Alexander Dekhtyar, dekhtyar@calpoly.edu, 14-215

Office Hours:

When		Who	Where
Tuesday	11:00 - 12:00pm	Alex	14-215
Wednsday	9:00am - 11:00am	Alex	14-215
Thursday	11:00 - 12:00pm	Alex	14-215

Additional appoinments: send email.

Final Exam Date: Tuesday, December 6, 2011, 7:10--10:00pm

(note: there is no final exam, but we will do project presentations in that time)

News and Notes

• Project teams are listed here. Photographs from the project fair are here.
  [September 30, 2011]

• Welcome to CSC 570! Here is the schedule for the upcoming two weeks:

  Day	Location	Instructor(s)	Class topic
  Tuesday, September 20	14-232B	Alex	Syllabus, algorithms
  Thursday, September 22	14-256 (SE Lab)	Anya Goodman	Intro to Bioinformatics
  Tuesday, September 27	14-232B	Alex	Simple bioinformatics problems
  Thursday, September 29	14-256 (SE Lab)	Anya Goodman, Chris Kitts, Michael Black	Project Fair

  [September 19, 2011]

Course Materials

Project

Project A	SuperGene Predictor	Anya Goodman	Description [doc]	[September 28, 2011]
Project B	Bacterial Strain Identification and Maintenance	Chris Kitts	Description [doc]	[September 28, 2011]
Project C	Pyroprint Simulation	Michael Black	Description [doc]	[September 28, 2011]
Project B			Background/CPLOP DB [doc]	[September 28, 2011]

Assignments

Assignment 1	Research presentation	Due: November 15/December 1	Postscript	PDF	[October 5, 2011]
Assignment 2	Project Deliverables	Due: December 6	Postscript	PDF	[November 22, 2011]

Lecture Notes Template

Presentation Schedule

Lecture Notes

Lecture 0	September 22	Bioinformatics in a nutshell	Postscript	PDF	[September 19, 2011]
Lecture 1	September 27	String Matching	Postscript	PDF	[September 27, 2011]
Lecture 2	October 4-6	Suffix Trees	Postscript	PDF	[October 4, 2011]
Lecture 3	October 6	Repeated Sequence/Palindrome Detection	Postscript	PDF	[October 19, 2011]
Lecture 4	October 11	Restriction Mapping	Postscript	PDF	[October 19, 2011]
Lecture 5	October 13	Motif Finding	Postscript	PDF	[October 19, 2011]
Lecture 6	October 18	Genome Rearrangement/Greedy Algorithms	Postscript	PDF	[October 19, 2011]

Papers

Exact String Matching

• Donald Knuth, James Morris, Vaughan Pratt, Fast Pattern Matching In Strings, SIAM J. Computation, Vol 6, No. 20, June 1977.
• Robert S. Boyer, J. Strother Moore, A Fast String Searching Algorithm, CACM, Vol. 20, No. 10, October 1977.

Approximate String Matching

• Gonzalo Navarro, A Guided Tour to Approximate String Matching, ACM Computing Surveys, Vol. 33, No. 1, pp. 31-88, March 2001.

Suffix Trees

• E. Ukkonen, On-line Construction of Suffix Trees, Algorithmica, Vol. 14, pp. 249-260, 1995.

Repeat/Palindrome Detection

• Roman Kolpakov, Gregory Kucherov, Searching for Gapped Palindromes, Theoretical Computer Science, Vol 410, pp. 5365--5373, 2009.
• Alexandre Porto, Valmir Barbosa, Finding Approximate Palindromes in Strings, Pattern Recognition 35(11): 2581-2591 (2002).
• Lloyd Allison, Finding Approximate Palindromes in Strings Quickly and Simply, Technical Report 2004/162 (Monash U., Australia), 23 November, 2004.
• Alberto Apostolico, Dany Breslauer, Zvi Galil, Parallel Detection of all Palindromes in a String, in Proc. STACS 94, Lecture Notes in Computer Science, 1994, Volume 775/1994.
• Ravi Gupta, Ankush Mittal, Vipin Narang, Wing-Kin Sung, Detection of Palindromes in DNA Sequences Using Periodicity Transform, Proc. IEEE International Workshop on Biomedical Circuits and Systems, 2004.

Parallel and Distributed Programming for Bioinformatics