Module 08776 (2002)

Syllabus page 2002/2003

06-08776
Algorithms & Methods for Bioinformatics
Level 2/I

x-apw
Peter Coxhead (coordinator)
10 credits in Semester 1

Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus

The Module Description is a strict subset of this Syllabus Page. (The University module description has not yet been checked against the School's.)

Relevant Links

None.

Outline

This module will provide an introduction to the information content of biological sequence data and the computational algorithms used to analyse such data.

Aims

The aims of this module are to:

  • provide an introduction to the information content of biological sequence data
  • introduce the computational algorithms used to analyse such data

Learning Outcomes

On successful completion of this module, the student should be able to: Assessed by:
1demonstrate an understanding of biological sequence data and the methods used to analyse it Examination
2use proprietary software to solve simple sequence alignment problems Coursework

Restrictions, Prerequisites and Corequisites

Restrictions:

None

Prerequisites:

None

Co-requisites:

None

Teaching

Teaching Methods:

2 hrs lectures, tutorials, practicals per week

Contact Hours:

24

Assessment

  • Supplementary (where allowed): As the sessional assessment
  • 1 hr examination (50%), coursework (50%). Resit by examination only.

Recommended Books

TitleAuthor(s)Publisher, Date
Beginning Perl for BioinformaticsTisdall, J.O'Reilly, 2001
Bioinformatics Computer SkillsGibas, C. & Jambeck, P.O'Reilly, 2001
Algorithms on Strings, Trees and SequencesGusfield, D.Cambridge University Press, 1997
Bioinformatics -- the Machine Learning ApproachBaldi, P. & Brunak, S.MIT Press, 1998

Detailed Syllabus

  1. Theoretical
    • Overall introduction. Exponentiation and logarithms. Information theory. Information content of biological sequences.
    • Introduction to pairwise alignment. The scoring model. Substitution matrices. Gap penalties.
    • Alignment algorithms. Global alignment: the Needleman-Wunsch algorithm. Computational complexity.
    • Local alignment: the Smith-Waterman algorithm. Repeated matches. Overlap matches.
    • Dynamic programming with more complex models. Alignment with affine gap scores. More complex FSA models.
    • Heuristic alignment algorithms. BLAST and FASTA. Linear space alignments. Significance of scores. BLOSUM matrices.
    • Introduction to HMMs. Markov chains. Modelling the ends of sequences. Using Markov chains for discrimination. Hidden markov models. Formal definition of an HMM.
    • Most probable state path: the Viterbi algorithm. The forward algorithm. The backward algorithm and posterior state probabilities. Posterior decoding.
    • Parameter estimation for HMMs. Estimation when the state sequence is known. Estimation when paths are unknown: Baum-Welch and Viterbi training.
    • Multiple sequence alignment methods. What a multiple alignment means. Scoring a multiple alignment. Minimum entropy. Sum of pairs: SP scores. Progressive alignment methods. The Feng-Doolittle algorithm.
    • Building phylogenetic trees. Distance metrics. Clustering algorithms. Making a tree from pairwise distances. UPGMA. Molecular clocks and the ultrametric property of distance.
    • Spare lecture slot for revision, remedial work, etc.
  2. Practical
    • Introduction to Perl. Representing sequence data. Command interpretation. Statements. Variables. Strings. Assignment. Output. Concatenating DNA fragments.
    • Transcription: DNA to RNA. Perl documentation. Producing the reverse complement of a strand of DNA. Arrays. Reading protein sequences from files. Scalar and list context.
    • Perl exercises.
    • Motifs and loops. Flow control. Conditional statements. Conditional tests and matching braces. Loops.
    • Open and unless. Finding motifs. Keyboard input. Turning arrays into scalars with join. Do-until loops.
    • Regular expressions. Character classes. Pattern matching. Counting nucleotides. Exploding strings into arrays. Operating on strings. Writing to files.
    • Perl exercises.
    • Programming project clinics (Java).

Last updated: 21 January 2001

Source file: /internal/modules/COMSCI/2002/xml/08776.xml

Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus