Opportunities for Combinatorial Optimization in Computational Biology

References

• Andorf C., Dobbs D., Honavar V. Discovering protein function classification rules from reduced alphabet representations of protein sequences. (2002) . Technical report, Department of Computer Science, Iowa State University, Ames, IAGoogle Scholar
• Atkins J., Hart W. E. On the intractability of protein folding with a finite alphabet of amino acids. Algorithmica (1999) 25:279–294Crossref, Google Scholar
• Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M.Complexity and Approximation. Combinatorial Optimization Problems and their Approximability Properties (1999) (Springer, Berlin, Germany) Google Scholar
• Babai L. Local expansion of vertex-transitive graphs and random generation in finite groups. Proc. ACM Sympos. Theory Comput. (STOC) (1991) (ACM Press, New York) 164–174Crossref, Google Scholar
• Backofen R.Optimization Techniques for the Protein Structure Prediction Problem (1999) . Ph.D. thesis Ludwig-Maximilians-Universität München, Institut für Informatik, München, GermanyGoogle Scholar
• Bader D. A., Moret B. M., Yan M. A linear-time algorithm for computing inversion distances between signed permutations with an experimental study. J. Comput. Biol. (2001) 8(5):483–491Crossref, Google Scholar
• Bafna V., Pevzner P. Genome rearrangements and sorting by reversals. SIAM J. Comput. (1996) 25:272–289Crossref, Google Scholar
• Bafna V., Pevzner P. Sorting by transpositions. SIAM J. Discrete Math. (1998) 11(2):224–240Crossref, Google Scholar
• Bafna V., Lawler E. L., Pevzner P. Approximation algorithms for multiple sequence alignment. Theoret. Comput. Sci. (1997) 182(1–2):233–244Crossref, Google Scholar
• Berger B., Leighton T. Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete. J. Comput. Biol. (1998) 5(1):27–40Crossref, Google Scholar
• Berman P., Karpinski M., Wiederman J., van Emde Boas P., Nielsen M. On some tighter inapproximability results. Automata, Languages and Programming, 26th International Colloquium, ICALP'99 Lecture Notes in Computer Science (1999) (Springer, Heidelberg, Germany) . No.1644Google Scholar
• Berman P., Hannenhalli S., Karpinski M. 1.375-approximation algorithm sorting by reversals. Proc. Annual Eur. Sympos. on Algorithms (ESA) Lecture Notes in Computer Science (2002) (Springer, Heidelberg, Germany) 200–210No.2461Crossref, Google Scholar
• Berman H., Westbrook J., Feng Z., Gilliland G., Bhat T., Weissig H., Shindyalov I., Bourne P. The protein data bank. Nucleic Acids Research (2000) 28:235–242The PDB is at http://www.rcsb.org/pdb/Crossref, Google Scholar
• Błażewicz J., Kasprzak M., Stema M., Weglarz J. Selected combinatorial optimization problems arising in molecular biology. Ricerca Operativa (1997) 26(80):35–63Google Scholar
• Bower J., Bolouri H.Computational Modeling of Genetic and Biochemical Networks (2001) (MIT Press, Cambridge, MA) Google Scholar
• Brown T.Genomes (1999) (John Wiley & Sons, New York) Google Scholar
• Byrd R., Eskow E., van der Hoek A., Schnabel R., Pardalos P., Shalloway D., Xue G. Global optimization methods for protein folding problems. Proc. DIMACS Workshop on Global Minimization Nonconvex Energy Functions: Molecular Conformation and Protein Folding, DIMACS Series in Discrete Mathematics and Theoretical Computer Science (1996) American Mathematical Society, Providence, RI:29–40Google Scholar
• Campbell A., Heyer L.Discovering Genomics, Proteomics, & Bioinformatics (2002) (Benjamin Cummings, San Francisco, CA) Google Scholar
• Caprara A. On the tightness of the alternating-cycle lower bound for sorting by reversals. J. Combin. Optim. (1999a) 3:149–182Crossref, Google Scholar
• Caprara A. Sorting permutations by reversals and Eulerian cycle decompositions. SIAM J. Discrete Math. (1999b) 12:91–110Crossref, Google Scholar
• Caprara A., Lancia G., Sankoff D., Nadeau J. H. Experimental and statistical analysis of sorting by reversals. Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment and Evolution of Gene Families (2000) 1(Kluwer Series in Computational Biology, Kluwer, Norwell, MA) 171–183Crossref, Google Scholar
• Caprara A., Lancia G., Ng S. Sorting permutations by reversals through branch and price. INFORMS J. Comput. (2001) 13(3):224–244Link, Google Scholar
• Carrillo H., Lipman D. The multiple sequence alignment problem in biology. SIAM J. Appl. Math. (1988) 48(5):1073–1082Crossref, Google Scholar
• Clark A. Inference of haplotypes from PCR—amplified samples of diploid populations. Mol. Biol. Evolution (1990) 7:111–122Google Scholar
• Clote P., Backofen R.Computational Molecular Biology (2000) (John Wiley & Sons, New York) Google Scholar
• Crescenzi P., Goldman D., Papadimitriou C., Piccolboni A., Yannakakis M. On the complexity of protein folding. J. Comput. Biol. (1998) 5(3):423–466Crossref, Google Scholar
• Dakla E., Latham A., Tecle E., Tsan G., Willis L.MIT Biology Hypertextbook (2004) . Massachusetts Institute of Technology http://web.mit.edu/esgbio/www/Google Scholar
• Delcher A., Kasif S., Fleischmann R., Peterson J., White O., Salzberg S. Fast algorithms for whole genomes. Nucleic Acids Res. (1999) 27(11):2369–2376Also see http://www.tigr.org/software/mummer/Crossref, Google Scholar
• Delcher A., Phillippy A., Carleton J., Salzberg S. Fast algorithms for whole genomes. Nucleic Acids Res. (2002) 30(11):2478–2483Crossref, Google Scholar
• Dill K. A. Theory for the folding and stability of globular proteins. Biochemistry (1985) 24:1501Crossref, Google Scholar
• Dill K. A., Bromberg S., Yue K., Fiebig K., Yee D., Thomas P., Chan H. Principles of protein folding—A perspective from simple exact models. Protein Sci. (1995) 4:561–602Crossref, Google Scholar
• Fuellen G.A Gentle Guide to Multiple Alignment (1997) . World Wide Web http://www.techfak.uni-bielefeld.de/bcd/Curric/MulAli/mulali.htmlGoogle Scholar
• Garey M., Johnson D.Computers and Intractability, a Guide to the Theory of NP-Completeness (1979) (W.H. Freeman and Co., San Francisco, CA) Google Scholar
• Genome The Genome International Sequencing Consortium, Initial sequencing and analysis of the human genome. Nature (2001) 409:860–921Crossref, Google Scholar
• Goldman D., Istrail S., Papadimitriou C. Algorithmic aspects of protein structure similarity. 40th Annual Sympos. Foundations Comput. Sci. (FOCS) (1999) (IEEE Computer Society Press, New York) 512–521Crossref, Google Scholar
• Golumbic M.Algorithmic Graph Theory and Perfect Graphs (1980) (Academic Press, New York) Crossref, Google Scholar
• Greenberg H.Mathematical Programming Glossary (1996–2003) . World Wide Web http://www.cudenver.edu/~hgreenbe/glossary/Google Scholar
• Greenberg H., Bar-Or R., Lana L., Miller C., Morrison T., van Woudenberg C. (2002) . Pathway inference: Computational issues. Mathematics clinic report, Mathematics Department, University of Colorado, Denver, CO. Available at http://www-math.cudenver.edu/clinic/report.shtmlGoogle Scholar
• Groetschel M., Lovasz L., Schrijver A. A polynomial algorithm for perfect graphs. Ann. Discrete Math. (1984) 21:325–356Google Scholar
• Gusfield D. Efficient methods for multiple sequence alignment with guaranteed error bounds. Bull. Math. Biol. (1993) 55:141–154Crossref, Google Scholar
• Gusfield D.Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology (1997) (Cambridge University Press, Cambridge, UK) Crossref, Google Scholar
• Gusfield D. Inference of haplotypes from PCR—amplified samples of diploid populations: Complexity and algorithms. (1999) . Technical report CSE-99-6, University of California, Department of Computer Science, Davis, CAGoogle Scholar
• Gusfield D., Altman R., Bailey T., Bourne P., Gribskov M., Lengauer T., Shindyalov I., Eyck L. T., Weissig H. A practical algorithm for optimal inference of haplotypes from diploid populations. Proc. Eighth Internat. Conf. Intelligent Systems Molecular Biol. (ISMB) (2000) (AAAI Press, Menlo Park, CA) 183–189Google Scholar
• Gusfield D. (2001) . XPARAL: Graphical computation of parameterized alignments. http://www.cs.ucdavis.edu/~gusfield/xparall/Google Scholar
• Gusfield D. Haplotyping by pure parsimony. (2003) . Technical report CSE-2003-2, Department of Computer Science, University of California, Davis, CAGoogle Scholar
• Hannenhalli S., Pevzner P. A. Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). Proc. ACM Sympos. Theory Comput. (STOC) (1995) (ACM Press, New York) 178–189(full version appeared in Journal of the ACM 46, 1–27, 1999)Google Scholar
• Hart W. E., Istrail S. Lattice and off-lattice side chain models of protein folding: Linear time structure prediction better than 86% of optimal. J. Comput. Biol. (1997a) 4(3):241–259Crossref, Google Scholar
• Hart W. E., Istrail S. Robust proofs of NP-hardness for protein folding: General lattices and energy potentials. J. Comput. Biol. (1997b) 4(1):1–20Crossref, Google Scholar
• Hunter L., Hunter L. Molecular biology for computer scientists. Artificial Intelligence & Molecular Biology (1993) (MIT Press, Cambridge, MA) 1–46Available at http://www.aaai.org/ Library/Books/Hunter/hunter.htmlGoogle Scholar
• Ideker T., Galitski T., Hood L. A new approach to decoding life: Systems biology. Annual Rev. Genomics Human Genetics (2001) 2:343–372Crossref, Google Scholar
• Jiang T., Lawler E., Wang L. Aligning sequences via an evolutionary tree: Complexity and approximation. Proc. Annual ACM Sympos. Theory Comput. (STOC) (1994) (ACM Press, New York) 760–769Crossref, Google Scholar
• Kaplan H., Shamir R., Tarjan R. E. Faster and simpler algorithm for sorting signed permutations by reversals. Proc. Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (1997) (ACM Press, New York) 344–351Crossref, Google Scholar
• Karp R. Mathematical challenges from genomics and molecular biology. Notices Amer. Math. Soc. (2002) 49(5):544–553Google Scholar
• Kececioglu J., Ravi R. Of mice and men: Algorithms for evolutionary distances between genomes with translocation. Proc. Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (1995) (ACM Press, New York) 604–613Google Scholar
• Kececioglu J., Sankoff D. Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement. Algorithmica (1995) 13:180–210Crossref, Google Scholar
• Khimasia M., Coveney P. Protein structure prediction as a hard optimization problem: The genetic algorithm approach. Molecular Simulation (1997) 19:205–226Crossref, Google Scholar
• Krasnogor N., López P. M., de la Canal E., Pelta D. Simple models of protein folding and a memetic crossover. Exposed at INFORMS CSTS, Computer Science and Operations Research: Recent Advances in the Interface Meeting (1998a) Google Scholar
• Krasnogor N., Pelta D., Lopez P. M., Mocciola P., de la Canal E., Alpaydin E., Fyfe C. Genetic algorithms for the protein folding problem: A critical view. Proc. Engrg. Intelligent Systems (1998b) (Academic Press, Reading, MA) Google Scholar
• Kurtz S. Reducing the space requirement of suffix trees. Software-Practice Experience (1999) 29(13):1149–1171Crossref, Google Scholar
• Lancia G.Optimization Problems in Computational Molecular Biology (1997) . Ph.D. thesis Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PAGoogle Scholar
• Lancia G., Bafna V., Istrail S., Lippert R., Schwartz R. SNPs problems, complexity and algorithms. Proc. Annual Eur. Sympos. Algorithms (ESA) Lecture Notes in Computer Science (2001a) 2161Springer, Heidelberg, Germany:182–193Crossref, Google Scholar
• Lancia G., Carr R., Walenz B., Istrail S. 101 optimal PDB structure alignments: A branch-and-cut algorithm for the maximum contact map overlap problem. Proc. Fifth Annual Internat. Conf. Comput. Biol. (2001b) (ACM Press, New York) 193–202Crossref, Google Scholar
• Lau K., Dill K. A lattice statistical mechanics model of the conformational and sequence spaces of proteins. Macromolecules (1989) 22:3986–3997Crossref, Google Scholar
• Lippert R., Schwartz R., Lancia G., Istrail S. Algorithmic strategies for the SNPs haplotype assembly problem. Briefings Bioinformatics (2002) 3(1):23–31Crossref, Google Scholar
• Molecular Biology NotebookMolecular Biology Notebook (2000) . Rothamsted Research World Wide Web http://www.iacr.bbsrc.ac.uk/notebook/courses/guide/Google Scholar
• Neumaier A. Molecular modeling of proteins and mathematical prediction of protein structure. SIAM Rev. (1997) 39:407–460Crossref, Google Scholar
• Ngo J., Marks J., Karplus M., Merz K., Grand S. L. Computational complexity, protein structure prediction, and the Levinthal paradox. The Protein Folding Problem and Tertiary Structure Prediction (1994) (Birkhäuser, Boston, MA) 433–506Ch. 14Crossref, Google Scholar
• Notredame C., Higgins D. SAGA: Sequence alignment by genetic algorithm. Nucleic Acids Res. (1996) 24(8):1515–1524Crossref, Google Scholar
• Nussinov R., Ma B., Wolfson H., Jiang T., Xu Y., Zhang M. Computational methods for docking and applications to drug design: Functional epitopes and combinatorial libraries. Current Topics in Computational Molecular Biology (2002) (MIT Press, Cambridge, MA) 502–524Google Scholar
• Patton A., Punch W., Goodman E., Eshelman L. A standard GA approach to native protein conformation prediction. Proc. Sixth Internat. Conf. Genetic Algorithms (1995) (Morgan Kauffman, San Francisco, CA) 574–581Google Scholar
• Pedersen C.Algorithms in Computational Biology (1999) . Ph.D. thesis. Department of Computer Science University of Aarhu, Denmark. Available at http://www.brics.dk/~cstorm/Google Scholar
• Pevzner P.Computational Molecular Biology (2000) (MIT Press, Cambridge, MA) Crossref, Google Scholar
• Piccolboni A., Mauri G. Application of evolutionary algorithms to protein folding prediction. Lecture Notes in Computer Science (1998) (Springer-Verlag, Heidelberg, Germany) 123–136No. 1363Crossref, Google Scholar
• Rabow A. A., Scheraga H. A. Improved genetic algorithm for the protein folding problem by use of a Cartesian combination operator. Protein Sci. (1996) 5:1800–1815Crossref, Google Scholar
• Rizzi R., Bafna V., Istrail S., Lancia G., Guigo R., Gusfield D. Practical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem. Proc. 2nd Annual Workshop on Algorithms in Bioinformatics (WABI), Lecture Notes in Computer Science (2002) (Springer-Verlag, Heidelberg, Germany) 29–43No. 2452Crossref, Google Scholar
• Sankoff D., Cedergren R., Abel Y. Genomic divergence through gene rearrangement. Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences (1990) (Academic Press, New York) 428–438Crossref, Google Scholar
• Setubal J., Meidanis J.Introduction to Computational Molecular Biology (1997) (Brooks/Cole, Pacific Grove, CA) Google Scholar
• Thompson J., Gibson T., Higgens D.Clustal W version 1.5 (1995) . World Wide Web http://www.cmbi.kun.nl/bioinf/CLUSTALW/clustalw-4.htmlGoogle Scholar
• Unger R., Moult J. A genetic algorithm for 3D protein folding simulations. Proc. Fifth Annual Internat. Conf. Genetic Algorithms (1993a) San Francisco, CA:581–588Google Scholar
• Unger R., Moult J. Genetic algorithms for protein folding simulations. J. Mol. Biol. (1993b) 231(1):75–81Crossref, Google Scholar
• Venter J. et al. The sequence of the human genome. Science (2001) 291:1304–1351Crossref, Google Scholar
• Wang L., Jiang T. On the complexity of multiple sequence alignment. J. Comput. Biol. (1994) 1:337–348Crossref, Google Scholar
• Wang L. S., Warnow T. Estimating true evolutionary distances between genomes. Proc. Annual ACM Sympos. Theory of Comput. (STOC) (2001) (ACM Press, New York) 637–646Crossref, Google Scholar
• Willis L.Biology Hypertextbook (2000) . Massachusetts Institute of Technology http://esg-www.mit.edu:8001/esgbio/Google Scholar
• Yue K., Dill K. A. Sequence-structure relationships in proteins and copolymers. Phys. Rev. E (1993) 48(3):2267–2278Crossref, Google Scholar
• Yue K., Dill K. A. Forces of tertiary structural organization in globular proteins. Proc. National Acad. Sci. (USA) (1994) 92:146–150Crossref, Google Scholar