This course introduces the foundations of algorithmic techniques and analysis, as motivated by biological problems. Topics include dynamic programming, tree and graph algorithms, sequence analysis, clustering and hidden markov models. Motivations include sequence alignment, motif finding, genome assembly, gene prediction, and phylogeny.
Class Meeting Time/Location
Time: Tue, Thu 2:15 pm - 3:30 pm
Where: Ritter Hall 106
Tae-Hyuk (Ted) Ahn, PhD
Department of Computer Science
Program of Bioinformatics and Computational Biology
Office: 305 Ritter Hall (Lab: 302 Ritter Hall)
Phone: (314) 977-3633
Office Hour: Mon 10 am - 11:30 am, Tue 12:30 pm - 2 pm or by appointment
Credits: 3 Credits Pre-requisites: The official prerequisite is a C- or better in BCB5200 and BCB5250.
Bioinformatics and Computational Biology research is getting bigger and huge, that touches upon many distinct algorithmic and biological area of study. We will try to cover important algorithmic techniques to solve biological questions. Here is a tentative list of topics I would like to cover this semster, but not necessarily in order.
- Sequence, string, and tree
- Algorithms for motif finding
- Assembly and graph algorithms
- Optimal sequence alignment and mapping
- Identifying genes and clustering
- Hidden Markov Model and applications
Student Learning Outcomes
After successfully complete this course, students are expected:
- Understand underlying fundamental concepts of computational biology.
- Analyze biological algorithms for asymptotic computation time and memory usage.
- Describe the fundamental algorithmic types used in biological contexts.
- Differentiate between sequence alignment algorithms and utilize the one most appropriate for the problem at hand.
- Utilize complex data structures to improve the efficiency of sequence analysis.
- Understand the use of discrete mathematical structures for biological algorithms.
Course Materials and Resources
The primary textbook for this course is “Bioinformatics Algorithms: An Active Learning Approach (3rd Edition)” by Phillip Compeau and Pavel Pevzner. The lectures and slides will introduce the topics and cover the majority of the information you will be expected to know. Further resources, where relevant, will be provided via links on this website accompanying the slides or lecture notes. However, you should use this textbook as a resource when you feel you need more information about a particular topic or when you wish to learn the material at a different pace than we cover in the course. There are other (non-required) textbooks that I personally recommend as references:
- An Introduction to Bioinformatics Algorithms (Neil C. Jones and Pavel A. Pevzner 2004)
- Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology (Dan Gusfield 1997)
- Genome Scale Algorithm Design (Mäkinen, Belazzougui, Cunial, Tomescu 2015)
- Biological Sequence Analysis (Durbin, Eddy, Krogh, Mitchinson 1998)
If, you’re from a discipline where you’ve not had a formal algorithms course, I strongly recommend you to get
- Algorithms is free electronic version of Algorithms by Jeff Erickson (CS at UIUC).
- Introduction to Algorithms (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein 2009 3rd Edition) to be a nice introduction to the algorithms.
https://biohpc.github.io/BCB5300F19/ will be used to announce schedules, slides, assignments, and news.
Students can enroll in the class with this link: http://rosalind.info/classes/enroll/117859412c/. It is free to register it. We will use the Rosalind for solving some programming assignments.
Our SLU CS GitLab or GitHub Classroom could be used to submit some assignments. The instructor will provide further info if we use the Git system.
Blackboard could be used to post grades.
Face-to-face contact in class and in office hours is most desirable. Yet email is a convenient form of communication as well. I try to respond to email promptly, including at least once each evening when possible. Email contact over the weekend will likely be more sporadic, although I will be sure to check at least once.
If your question involves your progress on a current programming assignment, my response will be more informative if you can point out the specific problem you have encountered, and if I am able to see all of your source code. Therefore I strongly suggest that you either attach all relevant files to the email or submit preliminary versions of such files through git system.
Computer and Cell Phone Policy
Computers (laptops) will be an integral part of this course, both inside and outside of class. However, out of courtesy to both the instructor and other students, please do not use the laptops or computers for non-class related activity. In particular, you do not need to be using a computer unless an exercise or in class activity requiring them is in progress.
You are unlikely to need cell phones during the course of lecture. Please ensure that your cell phone is set to vibrate or silent during lecture, and do not send text messages of any kind.
- Exam (50%)
- Midterm (25%): Tentative schedule: Thursday, Oct. 17th, 2019 at 2:15 pm (classroom)
- Final Exam (25%): Tentative schedule: Thursday, Dec. 5th, 2019 at 2:15 pm (classroom)
- Homework (50%) There will be homework due regularly throughout the semester. Some will be written problem sets, due on paper at the start of class. Some will be programming homework through automated coding challenges on the Rosalind Bioinformatics Textbook Track.
For all homeworks, you are allowed to required to submit individual solutions. However, I encourage all of you to work with another student, as the best way to learn this material is to discuss and problem solve in a small group. Verbatim copying (from another student or from the internet) is forbidden, so please be sure to write up your solutions on your own. (A good rule of thumb is to take notes when working in a group, but then write them up later solo without the notes, and just reference the notes if you forget any details.)
Letter grades will be based on each students overall percentage of awarded points according to the following formula.
Student percentage above 90% will result in a grade of A or better.
Student percentage above 87% will result in a grade of A- or better.
Student percentage above 83% will result in a grade of B+ or better.
Student percentage above 80% will result in a grade of B or better.
Student percentage above 77% will result in a grade of B- or better.
Student percentage above 73% will result in a grade of C+ or better.
Student percentage above 70% will result in a grade of C or better.
Student percentage above 67% will result in a grade of C- or better.
Student percentage above 60% will result in a grade of D or better.
Student percentage below 60% will result in a grade of F.
Any modification to this scale at the end of the year will be in favor of the students. That is we may later decide to award an A to a student who is slightly below the cutoff, but we certainly will not deny an A from someone who is above the cutoff.
No matter what curve I impose, I maintain that the minimum passing grade for this class is a 50% - so if your average is lower than that, you will fail this class.
In general, extra credit will not be assigned in this class. The homework assignments provided will be challenging enough for everyone, so I would like for students to focus on the assignments provided.
Upon occasion (and solely at the instructor’s discretion), some small extra credit activities may be included, either by announcement in class or as part of an assignment. Please keep in mind that the extra credit is unlikely to significantly affect your grade; if you are concerned about your final grade, it is much better to focus your energy on the regular assignment. Extra credit is solely designed to provide an opportunity to students who wish to explore the topics further.
Late homework will suffer a penalty of 10% for every hour they are late. For example, homework which is submitted one hour late is worth at most 90% of the total credit.
In unusual circumstances, such as extreme illness or injury (documented by a doctor’s note), family emergencies, etc., please contact the instructor as early as possible to arrange accomidations.
I am happy to regrade any assignmentss or exam problems which you think were unfair or incorrect. Please bring me the original assignment, plus a written explanation of your question or complaint, within two weeks of the time the paper in question is graded and returned to you.
Policies and Resources
In the context of this course, I encourage students to discuss general course material, which includes studying for exams, sharing notes if a student must miss class, and working on any practice problems which are assigned. You are also allowed to turn in homework assignments in pairs. I also encourage you to discuss problems with other students, but please be careful to write up all solutions separately and do not copy any material from another student. As a good rule of thumb, make sure to write your solutions without using any notes or papers written while talking to anyone other than your partner. Remember, you will be on your own in the exam, so it is in your own best interest to make sure that you really understand the material and can solve each problem on your own!
You are allowed to use outside sources of information in this class, including textbooks and webpages. If the complete and correct answer is on page 263 of the lecture notes, the best solution you can submit is “See page 263 of the lecture notes.” Period. However, if you find a solution from any other source, such as a web page, a journal paper, a different algorithms textbook, or your mom, you must rewrite the solution in your own words, and you must properly cite your sources. Assume the grader has access to all the official course material, but nothing else. While we strongly encourge you to use any outside source at your disposal, please remember that the homework is supposed to demonstrate that you understand of the material, not just how to use Google. (In particular, if you blindly copy an incorrect solution, don’t expect to get very many points for it!)
Students who violate academic integrity policies will be reported to the department, particularly in cases where relevant sources are not cited or in cases of direct copying of another student’s work. First time offenses on homework will result in a minimum of a failing grade on the assignment in question, with egregious or repeated offenses resulting in failure in the course. In addition, students may be referred to the College of Arts and Sciences for further disciplinary action.
A statement of minimum standards for student academic integrity at Saint Louis University is described here; I expect full compliance with the policies described.
Our course follows university level attendance policy.
Saint Louis University and its faculty are committed to supporting our students and seeking an environment that is free of bias, discrimination and harassment. If you have encountered any form of sexual misconduct (e.g. sexual assault, sexual harassment, stalking, domestic or dating violence), we encourage you to report this to the University. If you speak with a faculty member about an incident of misconduct, that faculty member must notify SLU’s Title IX coordinator, Anna R. Kratky (DuBourg Hall, room 36; firstname.lastname@example.org; 314-977-3886) and share the basic facts of your experience with her. The Title IX coordinator will then be available to assist you in understanding all of your options and in connecting you with all possible resources on and off campus.
If you wish to speak with a confidential source, you may contact the counselors at the University Counseling Center at 314-977-TALK. To view SLU’s sexual misconduct policy and for resources, please visit the Office of the General Counsel.
Please see the College of Arts and Sciences Syllabi statements. I am more than happy to accomodate any requested accommodations; come see me or get in touch via email if you have any questions.
Students with a documented disability who wish to request academic accommodations must contact Disability Services to discuss accommodation requests and eligibility requirements. Once successfully registered, the student also must notify the course instructor that they wish to access accommodations in the course.
Please contact Disability Services, located within the Student Success Center, at Disability_services@slu.edu or 314-977-3484 to schedule an appointment. Confidentiality will be observed in all inquiries. Once approved, information about the student’s eligibility for academic accommodations will be shared with course instructors via email from Disability Services and viewed within Banner via the instructor’s course roster.
Note: Students who do not have a documented disability but who think they may have one are encouraged to contact Disability Services.
Student Success Center
In recognition that people learn in a variety of ways and that learning is influenced by multiple factors (e.g., prior experience, study skills, learning disability), resources to support student success are available on campus. The Student Success Center assists students with academic-related services and is located in the Busch Student Center (Suite, 331). Students can visit the Student Success Center to learn more about tutoring services, university writing services, disability services, and academic coaching.
University Writing Services
Students are encouraged to take advantage of University Writing Services in the Student Success Center; getting feedback benefits writers at all skill levels. Trained writing consultants can help with writing projects, multimedia projects, and oral presentations. University Writing Services offers one-on-one consultations that address everything from brainstorming and developing ideas to crafting strong sentences and documenting sources. For more information, visit the Student Success Center or call the Student Success Center at 314-977-3484.
Basic Needs Security
Students in personal or academic distress and/or who may be specifically experiencing challenges such as securing food or difficulty navigating campus resources, and who believe this may affect their performance in the course, are encouraged to contact the Dean of Students Office (email@example.com or 314-977-9378) for support. Furthermore, please notify the instructor if you are comfortable in doing so, as this will enable them to assist you with finding the resources you may need.