References

Here is a list of the main papers as well as main books in the domain and introductory chapters in more general books:

1

A. Apostolico. String editing and longest common subsequences. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 2 Linear Modeling: Background and Application, chapter 8, pages 361-398. Springer-Verlag, Berlin, 1997.

2

A. Apostolico and Z. Galil, editors. Pattern matching algorithms. Oxford University Press, 1997.

3

R. Bellman. Dynamic Programming. Princeton University Press, 1957.

4

M. Crochemore and T. Lecroq. Pattern matching and text data compression algorithms. In Allen B. Tucker Jr., editor, The Computer Science and Engineering Handbook, chapter 8, pages 162-202. CRC Press Inc., Boca Raton, FL, 1996.

5

M. Crochemore and W. Rytter. Text algorithms. Oxford University Press, 1994.

6

R. Giancarlo. Dynamic programming: special cases. In A. Apostolico and Z. Galil, editors, Pattern matching algorithms, chapter 7, pages 201-236. Oxford University Press, 1997.

7

O. Gotoh. An improved algorithm for matching biological sequences. J. Mol. Biol., 162:705-708, 1982.

8

D. Gusfield. Algorithms on strings, trees and sequences: computer science and computational biology. Cambridge University Press, Cambridge, 1997.

9

D. S. Hirschberg. A linear space algorithm for computing maximal common subsequences. Commun. ACM, 18(6):341-343, 1975.

10

V. I. Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. Sov. Phys. Dokl., 6:707-710, 1966.

11

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

12

E. W. Myers. An overview of sequence comparison algorithm in molecular biology. Report TR-91-29, Department of Computer Science, University of Arizona, Tucson, AZ, 1991.

13

E. W. Myers and W. Miller. Optimal alignments in linear space. Comput. Appl. Biosci., 4(1):11-17, 1988.

14

S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol., 48:443-453, 1970.

15

D. Sankoff and J. B. Kruskal. Time warps, string edits, and macromolecules: the theory and practice of sequence comparison. Addison-Wesley, Reading, MA, 1983.

16

P. H. Sellers. On the theory and computation of evolutionary distance. SIAM J. Appl. Math., 26:787-793, 1974.

17

J. C. Setubal and J. Meidanis. Introduction to Computional Molecular Biology. PWS Publishing Company, 1997.

18

T. F. Smith and M. S. Waterman. Identification of common molecular sequences. J. Mol. Biol., 147:195-197, 1981.

19

G. A. Stephen. String searching algorithms. World Scientific Press, 1994.

20

M. S. Waterman. Mathematical methods for DNA sequences. CRC Press Inc., Boca Raton, FL, 1991.

21

M. S. Waterman. Introduction to Computational Biology. Chapman & Hall, 1995.

22

M. S. Waterman, T. F. Smith, and W. A. Beyer. Some biological sequence metrics. Adv. Math, 20:367-387, 1976.

e-mails: {Christian.Charras, Thierry.Lecroq}@laposte.net