Infobiotics (2006/2007)

Learning outcomes

This course provides the basic formal tools for both the representation of biological information in discrete terms and the algorithmic analysis of biological processes. The program is composed by three parts: i) discrete mathematical structures, ii) languages, grammars and automata, iii) DNA algorithms.

DISCRETE STRUCTURES:

- Natural numbers and numerical systems
- Induction and successions
- Prime numbers and Fibonacci numbers
- Strings and nucleotides sequences
- Trees and membrane systems
- Sets and relations
- Graphs and biological networks
- Functions and molecular population
- Variables and propositions
- Schemata and combinatorial formulas

LANGUAGES, GRAMMARS AND AUTOMATA:

- Formal Languages
- Grammars and biological aggregation
- Linear patterns
- Finite state automata
- Regular expressions
- Computability, semi-decidability, decidability
- Turing machine and Church thesis

DNA COMPUTING:

- Structure and representation of DNA
- Basic DNA operations
- Adleman experiment
- SAT and Lipton experiment
- Bioalgorithms solving SAT
- DNA extraction and recombination by XPCR

Oral exam