Page 88

References

Altschul, S.F., and B.W. Erikson, 1986, "Locally optimal subalignments using nonlinear similarity functions," Bull. Math. Biol. 48(5/6), 633-660.

Altschul, S.F., W. Gish, W. Miller, E.W. Myers, and D.J. Lipman, 1990, "A basic local alignment search tool," Journal of Molecular Biology 215, 403-410.

Arbarbanel, RM., P.R. Wieneke, E. Mansfield, D.A. Jaffe, and D.L. Brutlag, 1984, "Rapid searches for complex patterns in biological molecules," Nucleic Acids Research 12(1), 263-280.

Barker, W.C., D. George, H.-W. Mewes, F. Pfeiffer, and A. Tsugita, 1993, "The PIRInternational database," Nucleic Acids Research 21(13), 3089-3092.

Benson, D., D.J. Lipman, and J. Ostell, 1993, "GenBank," Nucleic Acids Research 21(13), 2963-2965.

Chao, K.-M., and W. Miller, 1994, "Linear-space algorithms that build local alignments from fragments," Algorithmica, in press.

Dayhoff, M.O., W.C. Barker, and L.T. Hunt, 1983, "Establishing homologies in protein sequences," Methods in Enzymology 91, 524-545.

Eppstein, D., Z. Galil, and R. Giancarlo, 1989, "Speeding up dynamic programming," Theoretical Computer Science 64, 107-118.

Feng, D.F., and R.F. Doolittle, 1987, "Progressive sequence alignment as a prerequisite to correct phylogenetic trees," Journal of Molecular Evolution 25, 351-360.

Fox, B., 1973, "Calculating the Kth shortest paths," INFOR J (Can. J. Oper. Res. Inf Process.) 11, 66-70.

Garey, M.R., and D.S. Johnson, 1979, Computers and Intractability: A Guide to the Theory of NP-Complete Problems, New York: W.H. Freeman Press.

Gotoh, O., 1982, "An improved algorithm for matching biological sequences," Journal of Molecular Biology 162, 705-708.

Horowitz, E., and S. Sahni, 1978, pp. 198-247 in Fundamentals of Computer Algorithms, New York: Computer Science Press.

Kannan, S.K., and E.W. Myers, 1993, "An algorithm for locating non-overlapping regions of maximum alignment score," Proceedings of the 4th Combinatorial Pattern Matching Conference, Springer-Verlag Lecture Notes in Computer Science 684, 74-86.

Landau, G.M., and J.P. Schmidt, 1993, "An algorithm for approximate tandem repeats," Proceedings of the 4th Combinatorial Pattern Matching Conference, Springer-Verlag Lecture Notes in Computer Science 684, 120-133.

Lathrop, RH., T.A. Webster, and T.F. Smith, 1987, "ARIADNE: A flexible framework for protein structure recognition," Commun. ACM 30, 909-921.

Lipman, D.J., and W.R. Pearson, 1985, "Rapid and sensitive protein similarity searches," Science 227, 1435-1441.

Masek, W.J., and M.S. Paterson, 1980, "A faster algorithm for computing string-edit distances," Journal of Computing Systems Science 20(1), 18-31.

Mehldau, G., and E.W. Myers, 1993, "A system for pattern matching applications on biosequences," CABIOS 9, 3, 299-314.

Page 89

Miller, W., and E.W. Myers, 1988, "Sequence comparison with concave weighting functions," Bull. Math. Biology 50(2), 97-120.

Miller, W., J. Ostell, and K.E. Rudd, 1990, "An algorithm for searching restriction maps," CABIOS 6,247-252.

Myers, E.W., 1994a, "Approximately Matching Context Free Languages," TR94-22, Department of Computer Science, University of Arizona, Tucson, Ariz.

Myers, E.W., 1994b, "A sublinear algorithm for approximate keywork searching," Algorithmica 12(4), 345-374.

Myers, E.W., and W. Miller, 1988, "Optimal alignments in linear space," CABIOS 4(1), 11-17.

Myers, E.W., and W. Miller, 1989, "Approximate matching of regular expressions," Bull. Math. Biol. 51(1), 5-37.

Sankoff, D., 1975, "Minimal mutation trees of sequences," SIAM Journal of Applied Mathematics 28(1), 35-42.

Smith, T.F., and M.S. Waterman, 1981, "Identification of common molecular sequences," Journal of Molecular Biology 147, 195-197.

Smith, T.F., and W.S. Fitch, 1983, "Optimal sequence alignments," Proceedings of the National Academy of Sciences USA 80, 1382-1386.

Waterman, M.S., and M. Eggert, 1987, "A new algorithm for best subsequence alignments with application to tRNA-rRNA comparisons," Journal of Molecular Biology 197, 723728.

Waterman, M.S., M. Eggert, and E. Lander, 1992, "Parametric sequence comparisons," Proceedings of the National Academy of Sciences USA 89, 6090-6093.

Waterman, M.S., T.F. Smith, and W.A. Beyer, 1976, "Some biological sequence metrics," Advances in Mathematics 20, 367-387.

Zhang, K., and D. Shasha, 1989, "Simple fast algorithms for the editing distance between trees and related problems," SIAM Journal on Computing 18, 1245-1262.