CMSC 423: BioinformaticsFall 2010Course objectives: Study interesting algorithms and methods for the analysis of biological data. We willcover string m atching algorithms, string searching, string pattern finding (e.g. gene finding, discovery ofprotein binding sites), genome assembly, phylogenetics, protein structure prediction, and several topics ofcurrent research interest in bioinformatics.Professor: Carl Kingsford, Office : C BCB 3113. Email: carlkcs.umd.edu. Office hours: Mondays 2:30-3:30. If you cannot attend office hours at this time, email me about scheduling a different time.Web page: http://www.cs.umd.edu/class/fall2010/cmsc423/. Grades will be posted on http://grades.cs.umd.edu/.Class time: Tue/Thr 9:30am-10:45pm in CSIC 2107.Textbook: An Introduction to Bioinformatics Algorithms by Neil C. Jones and Pavel A. Pevzner. TheMIT Press, 2004. ISBN: 0-262-10106-8. Unfortunately, because bioinformatics is a broad, new, and raplidlychanging field, there is no great textbook. The material in the textbook will be supplemented by lectureslides and handouts.Course work: There will be ∼ 5 homework sets of 3–5 problems each. There will be 2 in-class exams, eachnon-cumulative, and a comprehensive final. There will b e a multi-part group project. Approximate gradingweight: 10% for homeworks, 20% for each exam, 30% for the final, and 20% for the project. The class willbe graded on a curve.Homework policies:• Written problem sets are due at the start of class. No late homework will be ac cepted — turn inwhat you have completed. If you will miss class, turn in the homework early.• Answers to homework problems should be written concisely and clearly. Messy or poorly writtenhomeworks will not be graded. Typesetting homeworks with LaTeX is encouraged (but notrequired).• Homework problems that ask for an algorithm should present: a cle ar English description or pseudocodeof the algorithm, a convincing argument for why the algorithm is correct, and an estimate of the runningtime.• Graded homeworks should be picked up in class; if you miss the class when the homework is returned,please pick it up during office hours.• Regrade requests should be made in writing within 1 week of the homework being returned.• You may discuss the problems with classmates. You must list the names of the class memberswith whom you worked at the top of your homework. You must write up your ownsolution independently!Exam policies: Exams and the final will be c losed book, closed note. The midterms will be held in-classon September 30, 2010 and November 11, 2010. The final exam will be in-class at the time se t by theofficial university exam schedule.Project policies: Projects will be completed in small groups and will involve programming. You mayNOT copy or give code to other groups. Providing code and using code from other groups areboth academic integrity violations that generally receive the same punishment. You cannot incorporatecode from the internet into your projects. Submitted projects may be checked automatically forinappropriate co de use. More details about the projects will be available in a few weeks.1The maximum possible score of a project will be reduced by 10% for every day it is late. After 5 late days,the project will no longer be accepted.Excused absences: Students claiming an excused absence must apply in writing and furnish documentarysupport (such as from a health care professional who treated the student) for any assertion that the absencequalifies as an excused absence. The support should explicitly indicate the dates or times the student wasincapacitated due to illness. Self-documentation of illness is not sufficient to excuse the absence. Absencesfor religious observances must be submitted in writing to the instructor within two weeks of the start ofthe semester. The instructor is not under obligation to offer a substitute assignment or to give a student amake-up assessment unless the failure to perform was due to an excused absence. An excused absence foran individual typically do es not translate into an extension for team deliverables on a project.Academic accommodations: Any student eligible for and requesting reasonable academic accommoda-tions due to a disability is requested to provide, to the instructor in office hours, a letter of accommodationfrom the Office of Disability Support Services (DSS) within the first two weeks of the semester.Course evaluations: At the end of the semester, please fill out a course evaluation at http://www.courseevalum.umd.edu. Course evaluations are read and taken seriously.Academic honesty: All class work s hould be done independently unless explicitly indicated on the as-signment handout. You may discuss homework problems with classmates, but must write your solution byyourself. If you do discuss assignments with other classmates, you must supply their names at the top ofyour homework. Projects may be completed in teams as sp e cified on the project handout.No excuses will be accepted for copying others work (from the current or past semesters), and violations willbe dealt with harshly. Every year, many CS students are referred to the honor board, which is an unpleasantexperience for everyone and can seriously impact plans for graduate school, graduation, etc. Getting a badgrade is much preferable to cheating.To quote the honor council: “The University of Maryland, College Park has a nationally recognized Codeof Academic Integrity, administered by the Student Honor Council. This Code s ets standards for academicintegrity at Maryland for all undergraduate and graduate students. As a student you are responsible forupholding these standards for this course. It is very important for you to be aware of the consequences ofcheating, fabrication, facilitation, and plagiarism. For more information on the Code of Academic Integrityor the Student Honor Council, please visit http://www.shc.umd.edu.To further exhibit your commitment to academic integrity, remember to sign the Honor Pledge on allexaminations and assignments: ‘I pledge on my honor that I have not given or received any unauthorizedassistance on this examination (assignment).’”2Tentative ScheduleSequence Comparison & Dynamic Programming (3 weeks)• Dynamic programming• Longest common subsequence• Sequence alignment (local, global, semiglobal)• Space efficient sequence alignment• Multiple sequence alignment• RNA foldingSequence Search & String Data Structures (1.5