Objective
The course aim to introduce the algorithmic approach to solving problems correctly and efficiently. Algorithms are ubiquitous in bioinformatics and are often at the interface of computer science and biology. Well established algorithmic techniques will be studied as well as ways to encode them in a computer program using python.
Program
The course aim to introduce computational thinking and the algorithmic approach to solving problems correctly and efficiently. Algorithms are ubiquitous in bioinformatics and are often at the interface of computer science and biology. We will introduce the algorithmic approach and the theory of algorithms for studying correctness and efficiency, understanding what makes a good algorithm and how to classify them.
We will study characteristic algorithmic techniques and the related computational ideas that are relevant to the field of biology and how to select the most suitable to solve a given task. Topics covered include
- Searching algorithms
- Greedy Algorithms
- Dynamic programming algorithms
- Graph-based algorithms
- Divide-and-Conquer algorithms
- Clustering and Tree-based algorithms
We will work with Python and how to write a computer program encoding a given algorithm. We will work with Amazon’s AWS and how to use cloud resources to efficiently execute our python programs on large datasets.
The detailed program of the course and the corresponding material is available on the Google Classroom system and also through the web page of the instructor.
Reference book and material
- @jonasBionformatics: NEIL C. JONES AND PAVEL A. PEVZNER: An Introduction to Bioinformatics Algorithms, A Bradford Book, The MIT Press, Cambridge, Massachusetts, London, England, 2004.
Contact and discussion
All announcements and discussions will be carried out through Google Classroom qazymsj. In Google Classroom, you are going to find a link to a Telegram that we share to discuss and talk.
Tentative detailed program
| Theoretical lecture (usually Thursday) | Date | Material | Practical Lecture (usually Monday) | Date | Material |
|---|---|---|---|---|---|
| L1: Computational Thinking | 3/10/2024 | first_lecture.pdf | T1: Intro to Pandas for data manipulation and visualization. Visual Studio. | 7/10/2024 | Tutorial 1 |
| L2: Algorithms for Bioinformatics, Complexity of Algorithms, Recursion | 10/10/2024 | second_lecture.pdf Chapter 1 and 2 of jonesBionformatics | T2: Data manipulation and visualization (cont.) Recursion | 14/10/2024 | Tutorial 2 |
| L3: Sorting Problem | 17/10/2024 | third_lecture.pdf Selection Sort Chapter 2.6 of jonesBionformatics Merge Sort Chapter 7.1 of jonesBionformatics QuickSort Chapter 12.1 of jonesBionformatics | T3: Git and Github Sorting exercises in Python [ Assignment 1 release ] | 21/10/2024 | Tutorial 3 |
| L4: Greedy Algorithms | 24/10/2024 | fourth_lecture.pdf Chapter 5 of jonesBionformatics | T4: Biopython Exercises on Greedy Algorithms | 28/10/2024 | Tutorial 4 |
| --- | 31/10/2024 | --- | L5: Introduction to Dynamic Programming T5: Exercises on Dynamic Programming [ Assignment 2 release ] | 4/11/2024 | Chapter 6.1, 6.2, 6.3 of jonesBionformatics fifth_lecture.pdf Tutorial 5 |
| L5 (cont.): Sequence Similarity Problems Edit Distance in Python T5 (cont.): Biopython for sequence alignment | 7/11/2024 | Chapter 6.4, 6.5, 6.6 of jonesBionformatics fifth_lecture.pdf Tutorial 5 | --- | 11/11/2024 | --- |
| L6: Divide and conquer algorithms: Binary search, Merge Sort (again) and Map Reduce | 14/11/2024 | Chapter 7.1 of jonesBionformatics sixth_lecture.pdf Map Reduce tutorial | T6: Exercises on Dynamic Programming and Divide-and-Conquer | 18/11/2024 | Tutorial 6 |
| L7: Graph Algorithms Intro to NetworkX [ Assignment 3 release ] | 21/11/2024 | Chapter 8.1 of jonesBionformatics graphs.pdf seventh_lecture.pdf Notebook on NetworkX | T7: Graph Algorithms on NetworkX | 25/11/2024 | graphs.pdf eigth_lecture.pdf Tutorial 7 |
| L8: Clustering algorithms | 28/11/2024 | Chapter 10.1, 10.2, 10.3 of jonesBionformatics ninth_lecture.pdf | --- | 2/12/2024 | --- |
| T8: Exploratory Data Analysis and Clustering Algorithms [ Assignment 4 release ] | 5/12/2024 | Tutorial 8 | T8: Exploratory Data Analysis and Clustering Algorithms (cont.) L9: Cloud computing Bash script | 9/12/2024 | Tutorial 8 (cont.) cloud_lecture.pdf |
| T9: Academy Cloud Foundations, Learner Lab | 12/12/2024 | L10: Oral interview description [ Assignment 5 release ] | 16/12/2024 | Available on Google Classroom | |
| [ Assignment 5 release ] | 7/1/2025 |
Evaluation
A total of five assignments will be handed over during the semester. These assignments are done by each student individually.
The course will be evaluated based on the performance of (a) the individual assignments, (b) the active participation of the student during the semester and (c) an oral interview.
I will upload detailed information on what you are expected to submit, how and when for each of the individual assignment, by following the instructions under the web page of each assignment.
Assignment rules
A total of five assignments will be handed over. These assignments are done by each student individually. Clearly you should discuss with other students of the course about the assignments. However, you must understand well your solutions and the final writeup must be yours and written in isolation. In addition, even though you may discuss about how you could implement an algorithm, what type of libraries to use, and so on, the final code must be yours. You may also consult the internet for information, as long as it does not reveal the solution. If a question asks you to design and implement an algorithm for a problem, it’s fine if you find information about how to resolve a problem with character encoding, for example, but it is not fine if you search for the code or the algorithm for the problem you are being asked. For the projects, you can talk with other students of the course about questions on the programming language, libraries, some API issue, and so on, but both the solutions and the programming must be yours. If you have violated the policy and you have copied in any way you will automatically fail. If you have any doubts about whether something is allowed or not, ask the instructor.
Assignments
| Assignments | Deadline | Statistics |
|---|---|---|
| Assignment 1 | November 3rd, 23:59 Rome/Europe time | |
| Assignment 2 | November 17th, 23:59 Rome/Europe time | At the bottom of the page ‘Assignment 2’ |
| Assignment 3 | December 4th, 23:59 Rome/Europe time | |
| Assignment 4 | December 20th, 23:59 Rome/Europe time | |
| Assignment 5 | January 19th, 23:59 Rome/Europe time |
Oral Interview
The procedure with which the oral interview will be conducted is going to be defined and explained to the class during a lecture. The guidelines on how the oral interview is structured are available on Google Classroom.
| Exam | Date |
|---|---|
| January | 27th |
| February | 17th |