CSC 550   For graduate students taking CSC 550, the ability to perform problem reduction (reducing new problems to known solved problems) will also be acquired through problem solving on homeworks.

(The University Library's ebook for the above required text, which provides free access for students, is available here.)

• Hans-Joachim Böckenhauer and Dirk Bongartz,
  Algorithmic Aspects of Bioinformatics,
  Springer-Verlag, Berlin, 2007.
  (Surveys combinatorial algorithms in computational biology.)
  
  
• Peter Clote and Rolf Backofen,
  Computational Molecular Biology: An Introduction,
  John Wiley and Sons, Chichester, England, 2000.
  (Broad coverage of recent material with an emphasis on probability and optimization.)
  
  
• Richard Durbin, Sean Eddy, Anders Krogh, and Graeme Mitchison,
  Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids,
  Cambridge University Press, New York, 1998.
  (Emphasizes hidden Markov models for sequence comparison.)
  
  
• Dan Gusfield,
  Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology,
  Cambridge University Press, New York, 1997.
  (Clear exposition of exact string matching.)
  
  
• Veli Mäkinen, Djamal Belazzougui, Fabio Cunial, and Alexandru Tomescu,
  Genome-Scale Algorithm Design: Biological Sequence Analysis in the Era of High-Throughput Sequencing,
  Cambridge University Press, Cambridge, United Kingdom, 2015.
  (More recent treatment of DNA sequence analysis.)
  
  
• Pavel Pevzner,
  Computational Molecular Biology: An Algorithmic Approach,
  MIT Press, Cambridge, Massachusetts, 2000.
  (In-depth treatment of genome rearrangements.)
  
  
• David Sankoff and Joseph Kruskal, editors,
  Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison,
  Addison-Wesley, Reading, Massachusetts, 1983.
  (A classic collection on sequence comparison and its applications.)
  
  
• João Setubal and João Meidanis,
  Introduction to Computational Molecular Biology,
  PWS Publishing, Boston, 1997.
  (A broad survey of computational biology for computer scientists.)
  
  
• Wing-Kin Sung,
  Algorithms for Next Generation Sequencing,
  Chapman and Hall, Boca Raton, Florida, 2017.
  (Focuses on DNA sequence assembly.)
  
  
• Michael Waterman,
  Introduction to Computational Molecular Biology: Maps, Sequences and Genomes,
  Chapman and Hall, London, 1995.
  (In-depth treatment of the statistics of sequence comparison.)

• Multiple sequence alignment:  tutorial notes
• Multiple sequence alignment:  Opal talk  (paper)
• Multiple sequence alignment:  AlignAlign talk  (paper)
• Systems biology:  Freeia talk  (factories paper)  (hyperpaths paper)

• Homework 1 (450, 550) (partial solutions), due September 27 by 5:00pm.
  
• Homework 2 (450, 550) (partial solutions), due October 11 by 5:00pm.
  
• Homework 3 (450, 550) (partial solutions), due November 12 by 5:00pm.
• Homework 4 (optional) (450, 550) (partial solutions), due November 26 by 2:00pm.

• Midterm exam (450/550), due October 17 by 11:59pm.

• Term paper, due December 16 by 5:30pm.

Course grades use the regular scale of A, B, C, D, and E. Grades are determined from a weighted average of the percentage of points earned on homeworks, the midterm exam, and the term paper for the final project.

30%   Homeworks 40%   Midterm exam 30%   Final project

Attaining a weighted score of at least 90% guarantees an A in the course, at least 80% guarantees a B, at least 70% guarantees a C, and at least 60% guarantees a D. These thresholds may be lowered, but will not be raised.

The awarding of points on homework and exam questions is roughly according to the following scheme. Having the right solution idea and the right technical execution of this idea earns at least 90%. (Only a perfect write-up that cannot be improved earns 100%.) Having the right idea but with errors in its execution is at least 80%. Having the wrong idea and errors in its execution, but demonstrating comprehension of the material, is at least 70%. Having the wrong idea, errors in execution, and deficiencies in comprehension, is roughly 60%. Work that shows no understanding is roughly 50%.

On homework and exam questions, writing an answer that relates to the question guarantees at least 50% of the points for the question (which is a failing percentage). No points are awarded for writing nothing.

Homeworks may contain bonus problems. Points earned on bonus questions are not added to points for required questions. Bonus points are tallied separately at the end of the semester, and considered subjectively as a measure of effort when deciding whether to move up a student who is near a letter-grade boundary.

On homework, very-high-level ideas can be discussed with friends, but solutions must represent individual work and must be written up separately. Use of solutions from previous offerings of the course is not permitted. Any material from the Internet that is used in a solution must be cited by its URL; to not cite it is plagiarism, which is considered cheating. (For more information, see the Department of Computer Science Course Policy on Collaboration and the University Code of Academic Integrity.)

When turning in solutions to homeworks, start each problem on a separate page, and put the problems in the correct order. Neatness, and especially conciseness, is required to earn the highest marks. If a problem eludes solution, state this up front and write down only what you know to be correct. Rambling at length about attempts that didn't succeed may result in more points being deducted.

Homework that is late (submitted after the due date and time) is not accepted.

Convened 400/500-level course   In this co-convened course, for graduate students taking CSC 550, the problems on homeworks and exams will be at a more challenging level of difficulty than for undergraduate students taking CSC 450. Other than this difference, the lectures, assignments, and grading are the same for both CSC 450 and CSC 550.

Incomplete or withdrawal   Requests for an incomplete (I) or withdrawal (W) must be made in accordance with University policies, which are available here.

Regrades   Requests for regrades of homeworks or exams must be submitted within one week of receiving the graded homework or exam.

The attendance policy is that you are allowed one unexcused absence in the first week, two unexcused absences in the first four weeks, and four unexcused absences in the first eight weeks. On exceeding these limits, you may be dropped from class.

I   String matching

• Suffix arrays:  Exact string matching using suffix arrays; linear-time construction; height array construction.
• Ferragina-Manzini index:  Optimal string matching using the Ferragina-Manzini index; the Burrows-Wheeler transform.
• Applications:  Solving diverse string matching problems using suffix arrays and the Ferragina-Manzini index.

II   Sequence alignment

• Two-sequence alignment:  Local and global alignment; affine gap costs; linear-space alignment; inverse parametric alignment.
• Multiple-sequence alignment:  Models of multiple sequence alignment; exact algorithms, approximation algorithms, heuristics; parameter advising.

III   Pathway inference

• Shortest hyperpaths:  Inferring systems of reactions that produce target molecules from source compounds via shortest hyperpaths in directed hypergraphs.
• Shortest factories:  Inferring reactions that produce targets from sources while conserving or not depleting intermediate metabolites via shortest factories in metabolic networks.

To foster a positive learning environment, students and instructors have a shared responsibility. We want a safe, welcoming, and inclusive environment where all of us feel comfortable with each other and where we can challenge ourselves to succeed. To that end, our focus is on the tasks at hand and not on extraneous activities (such as texting, chatting, reading a newspaper, making phone calls, web surfing, and so on).

Students are asked to refrain from disruptive conversations with people sitting around them during lecture. Students observed engaging in disruptive activity will be asked to cease this behavior. Those who continue to disrupt the class will be asked to leave lecture or discussion and may be reported to the Dean of Students.

Some learning styles are best served by using personal electronics, such as laptops and iPads. These devices can be distracting to other learners. Therefore, students who prefer to use electronic devices for note-taking during lecture should use one side of the classroom.

Please also watch the video available here.

• Absence and class participation policies
• Threatening behavior policy
• Accessibility and accommodations policy
• Code of academic integrity
• Nondiscrimination and anti-harrassment policy

• Department code of conduct
• Class recordings
• Illnesses and emergencies
• Obtaining help
• Preferred names and pronouns
• Confidentiality of student records
• Additional resources

Information contained in the course syllabus, other than the grade and absence policy, may be subject to change with advance notice, as deemed appropriate by the instructor.

The grade distributions for the Term Paper, and for the Overall course score, have been posted above.

The final response rate for the SCS survey at the end of Wednesday, December 11, reached 72.41%.

(Please complete the SCS survey on course feedback. If the response rate is at least 80% by December 11 at 5pm, all enrolled students will receive 5 bonus points.)