Computer Science Course Information
Back to CS Home Page

Computer Science Course Information

Level >Graduate >FALL_2005 >List >

Bioinformatics-Centric Data Structures & Algorithms

Course No. CIS 615
Sections 101
Title Bioinformatics-Centric Data Structures & Algorithms
Course Website
Prerequisite(s) None. However, experience and knowledge in object oriented programming is highly recommended
Instructor Qun Ma
  • Office Room No. : GITC 3801
  • Office Phone : 973-642-4497
  • Fax : 973-596-5777
  • Email :
  • Website:
  • Lab : The Applied Bioinformatics Laboratory
  • Instructor Office Hours

    Description This course is organized in a bioinformatics-centric manner. It helps to equip students with knowledge and skills in data structures and (non-numerical) algorithms for solving challenging problems arising from Bioinformatics. This course will cover algorithmic techniques such as recursion, divide-and-conquer, greedy and dynamic programming; algorithms such as sorting, tree and graph searching, network flow, biological sequence matching and comparison, genome sequencing and assembly, and biological database searching; and data structures such as lists, stacks, queues, heaps, hashes, trees and graphs. The learning experience of the students will be enriched by open-ended projects, which will involve significant programming.

    Topics Week 1. (a) Motivation and overview of data structures and algorithms and their roles in solving bioinformatics problems;
    (b) Objects and C++ and Java programming review

    Week 2. (a) Phylogenetics I: Big-Oh notation;
    (b) Unix/Linux and genomic Perl tutorials

    Week 3. (a) Phylogenetics II: divide-and-conquer
    (b) Exponential growth: Towers of Hanoi

    Week 4. Biological database management: sorting algorithms

    Week 5. Naive DNA/protein sequence alignment: exact matching

    Week 6. Optimal alignment of DNA/protein sequences: dynamic programming

    Week 7. Sequencing and assembly: shot-gun and GigAssembler, BLAST heuristics for approximate string matching, and biological database search

    Week 8. Midterm Exam

    Week 9. Trees in bioinformatics I: binary search trees, RB trees and B-trees

    Week 10. Trees in bioinformatics II: suffix trees

    Week 11. (a) Protein modeling: graphs and their traversals;
    (b) Amortized analysis

    Week 12. Network flow problems

    Week 13. Pathways and networks: single source shortest paths and other greedy algorithms

    Week 14. Selected topics in Bioinformatics

    Week 15. Presentations of Final Projects

    Text Book(s) (1) Computer Algorithms: Introduction to Design and Analysis (3rd edition) by Baase and Van Gelder, Addison Wesley Longman, 2000, ISBN 0-201-61244-5.

    (2) Genomic Perl: From Bioinformatics Basics to Working Code by Dwyer, Cambridge Press, 2003, ISBN 0-521-80177-X
    Time & Place Thursdays 6:00 PM - 9:05 PM Fac 319
    Other Info References:

    Jewels of Stringology by Crochemore and Rytter. World Scientific Pub Co, Paper back, 2003, ISBN 9-810-24897-0.

    Registrar's Website