Complexity Issues in Bioinformatics
Biology’s dilemma: There is too much to know about living things
Some important model organisms
Let’s find out everything about some species
Some genome sizes
Sequencing Genomes
Where to store all these data?
What’s in the databases?
Time-complexity of algorithms
Consequences of database growth
How to overcome the problem?
You have sequenced your genome - what do you do with it?
From genes to proteins
What did the gene finding algorithms find?
So we know the genes - do we know everything?
Prediction of gene function
How to detect similarity of genes?
Example of an alignment
How to score an alignment
Prediction of gene function: homology searches
Prediction of important sites in proteins
How to predict binding sites from sequence data:
Example of a multiple alignment
How to score multiple sequence alignments?
Computational complexity of multiple sequence alignment
The class P
The class NP
The P = NP problem
Polynomial-time approximation schemes
A few words about the proof
An open question
An partial answer
The practice of multiple sequence alignment
Using genomic data for reconstruction of phylogenies
Reconstructing phylogenies: How to get started
Methods for reconstruction of phylogenies
The computational challenge for reconstruction of phylogenies
Reconstruction of phylogenies: A success story
Gene interactions: Collecting gene expression data
Gene interactions: Interpeting gene expression data
Interpeting gene expression data: A mathematical challenge
Gene expression profiles: A success story
Email: just@math.ohiou.edu
Home Page: http://www.math.ohiou.edu/~just
Download presentation source