Bioinformatics

Module code: 7CCSMADA
Credit level: 7
Credit value: 15
Semester:  Semester 1 (autumn) 

Aims
To introduce strategies for the design of algorithms which are efficient in terms of time and space requirements.

Learning Outcomes
On successfully completing this module you should understand the basic techniques for designing algorithms for fundamental computational problems.

Provisional Syllabus
Introduction:
Algorithms and computational complexity
Asymptotic notation
Pseudocode
Algorithm design techniques:
Divide-and-Conquer: Quicksort
Dynamic programming: matrix chain multiplication
Greedy algorithms: Huffman codes
Order statistics:
Selecting the k-th smallest element of a list - a practical method
Selecting the k-th smallest element of a list - an optimal method
Lower bound on the time complexity of computing the median
Data structures for set manipulation problems:
Fundamental operations on sets
The union-find algorithm
Partitioning
Representations of directed and undirected graphs:
Adjacency-matrix and adjacency-list representations
Breadth-first and depth-first search using adjacency lists
Computing connected components of a graph
Strongly-connected and biconnected components
Topological sorting
Algebraic algorithms:
Strassen matrix multiplication algorithm
The Four Russians boolean matrix multiplication
Winograd's algorithm
LUP decomposition of matrices
Applications of LUP decomposition
Integer and polynomial arithmetic:
Integer and polynomial multiplication and division
Greatest common divisors and Euclid's algorithm
Chinese remaindering

Module code: 7CCSMCMB
Credit level: 7
Credit value: 15
Semester:  Semester 2 (spring) 

Aims
To understand the major concepts and problems of computational molecular biology. To appreciate the importance of these concepts in a wide diversity of practical applications. To learn which of the computational molecular biology problems have efficient algorithmic solutions and which are intractable (for example, which belong to the NP-complete complexity class). For some intractable problems, to understand how heuristic approaches to problem solutions may yield fast but only approximate solutions.

Learning Outcomes
On completing the module you should be able to design exact and efficient algorithms as well as approximation schemes and heuristics for some of the most important algorithms underlying the field of computational molecular biology, or bioinformatics. You will also be able to reason why efficient algorithms for certain problems might not be possible.

Provisional Syllabus
Basic concepts: Definitions and notions from Molecular Biology; DNA Sequence Analysis
Alignement:
Hamming and Levenshtein distances
Dynamic programming algorithm
Hirschberg's algorithm
Substitution matrices (BLOSSUM, PAM) and scoring
Seq vs Seq (Fasta, Dynamic Programming)
Seq vs Databank (BLAST)
Whole genome alignment
Multiple sequence alignment
Approximate string matching:
String matching with "don't cares"
Searching with differences
Searching with mismatches
Fragment assembly:
Shotgun sequencing
Gene detection:
Regular expressions, acceptor and donor sites
Alternative splicing
Secondary structure prediction:
RNA structure
Minimal free energy (Zuker's approach)
Protein Folding
Phylogeny:
Mapping and rearrangements
Clustering and classification techniques

Module code: 7CCSMART
Credit level: 7
Credit value: 15
Semester:  Semester 1 (autumn) 

Aims
To teach you to read and understand research papers and research lectures on your own, and pursue a research topic.

Learning Outcomes
You should obtain a good understanding of a particular technical area at a level that goes substantially beyond the taughts MSc materia.  You should also learn to explore a research area, to identify the important issues and understand their connection with each other and to demonstrate your technical understanding by presenting the results to a scientifica audience.

Provisional Syllabus
In this optional module, you will study advance research literature preferably in an area that is related to the material taught in your programme.

7CCSMART is a first-term module, with work starting at the beginning of the first term, but with the assignment continuing into the second term. Lectures will cover research methods, report/paper writing, and presentation techniques. You must attend at least five selected research seminars during the first term and read several related research papers.

You must agree your choice of research topic with the module organiser, which must be on a topic of in the research area of one of the members of the Department. Towards the end of the first term, you must submit a first draft of a report (approximately 10-15 pages), which will be reviewed by the organiser and other students. The final draft of the report must be submitted in the second term. The submitted report forms the basis of the assessment.

Topics will include:
Doing Research
Writing
Writing Scientific Papers
Presenting Scientific Papers
References
Sources
Refereeing

Module code: 7CCSMDSI
Credit level: 7

The aims of this course are to present properties, implementations, and applications of fundamental and advanced data structures required for the efficient representation, organisation, searching, and manipulation of computer data. The course uses the C++ programming language as the implementation environment.

Module code: 7CCSMDBT
Credit level: 7

To study present and predicted developments in database technology from a formal perspective.

Module code: 7CCSMGPR
Credit level: 7

To provide the experience of working in a syndicate to design, implement and document a substantial software product.

Module code: 7CCSMTSP
Credit level: 7
Credit value: 15
Semester:  Semester 2 (spring) 

Aims
This unit is devoted to algorithms processing strings and texts efficiently. These types of algorithms are used for software design in the domains of operating systems utilities, search engines on the Internet, data retrieval systems, analysis of genetic sequences, and natural language processing, for example.

Learning Outcomes
On completing the module, you should be able to design and implement exact and efficient algorithms for matching patterns in textual data, building indexes for files, and more generally for solving algorithmic problems on strings and sequences.

Provisional Syllabus
Basic concepts:
Periods in strings
Finite automata and regular expressions
Exact pattern matching:
Brute-force algorithms for pattern matching
The Knuth-Morris-Pratt algorithm
The Boyer-Moore algorithm
The Karp-Rabin algorithm
Horspool's algorithm
Multiple pattern matching:
The Aho-Corasick automaton
Two-dimensional pattern matching
Structures for indexes:
Suffix arrays
Suffix trees
Suffix automata
Regular Pattern Matching
From regular expression to automata
Simulation of deterministic automata