Optimization in Bioinformatics
Three familiar problem areas, cast in our terminology
Sequence alignment RNA folding Mass spectrometry
Universe all possible alignments of all possible sequences all RNA secondary structures for all RNA molecules precise mass spectra of a known protein p
problem parameters two unaligned sequences x, y one particular RNA sequence x peak list from MS experiment with unknown protein x
candidates all possible alignments of x and y all legal structures of x under the rules of base pairing (C-G, A-U, G-U) all mappings between peaks of p and x
score 1 count aligned identical residues count number of base pairs peaks of same mass
choice 1 maximize identity maximize base pairs maximize count
score 2 account for residue similarity and gaps apply thermodynamic energy model relate peaks of similar mass
choice 2 maximize similarity minus gap score minimize free energy minimize mass of unrelated peaks
background image
university bielefeld AG PI BiBiServ
ambient picture