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 |