@article{ahu:lcs,
  author = "Aho, A. V. and Hirschberg, D. S. and Ullman, J. D.",
  title = "Bounds on the Complexity of the Longest Common
Subsequences Problem",
  journal = "Journal of the Association for Computing Machinery",
  volume = "23",
  year = "1974",
  pages = "1--12"}

@article{arnold,
  author = "Arnold, B. C.",
  title = "The Waiting Time Until First Duplication",
  journal = "Journal of Applied Probability",
  volume = "9",
  number = "4",
  year = "1972",
  pages = "841--846"}

@article{arratia-waterman,
  author = "Arratia, R. and Waterman, M. S.",
  journal = "Advances in Mathematics",
  volume = "55",
  year = "1985",
  pages = "13--23",
  title = "An {Erd\H{o}s}-{R\'enyi} Law with Shifts"}


@article{baer-brock,
  author = "Baer, R. M. and Brock, P. ",
  title = "Natural Sorting over Permutation Spaces",
  journal = "Mathematics of Computation",
  volume = "22",
  year = "1968",
  pages = "385--410",
  annote = "calculates values of $R_n$ and conjectures $2\sqrt{n}$ limit"}

@article{boyer-moore,
  author = "Boyer, R. S. and Moore, J. S.",
  title = "A Fast String Searching Algorithm",
  journal = "Communications of the Association for Computing
Machinery",
  volume = "20",
  year = "1977",
  pages = "762--772"}

@techreport{bradley-bradley,
  author = "Bradley, D. W. and Bradley, R. A.",
  title = "Application of Sequence Comparison to the Study of Bird
Songs",
  year = "1978",
  institution = "Department of Data Processing, California State
University, Long Beach, CA "}

@techreport{chvatal-sankoff:tr,
  author = "Chv\'atal, V. and Sankoff, D.",
  title = "Longest Common Subsequences of Two Random Sequences",
  institution = "Computer Science Department, Stanford University",
  number = "STAN-CS-75-477",
  year = "1975",
  keywords = "common subsequences, random sequences, matches",
  commentnote =  "copy of the Chvatal \& Sankoff paper"}

@article{chvatal-sankoff:jap,
  author = "Chv\'atal, V. and Sankoff, D.",
  title = "Longest Common Subsequences of Two Random Sequences",
  journal = "Journal of Applied Probability",
  volume = "12",
  year = "1975",
  pages = "306--315",
  keywords = "Random sequences, longest common subsequences, matches",
  commentnote =  "Seminal paper on LCS, a copy of their Stanford tech.rept.
Results are 
1) $\EX{\it LCS}$ for length $n \le 5$ and $k$
2) $\EX{\it LCS}$ for length $n \le 10$ and $k=2$
3) Lower bounds on match fraction (rational polynomial)
4) Simulation of match fraction as $n\to \infty$"}

@techreport{ckk:comb-prob,
  author = "Chv\'atal, V. and Klarner, D. A. and Knuth, D. E.",
  title = "Selected Combinatorial Research Problems",
  number = "STAN-CS-72-292",
  year = "1972",
  institution = "Stanford University"}

@article{deken,
  author = "Deken, J. G.",
  title = "Some Limit Results for Longest Common Subsequences",
  journal = "Discrete Mathematics",
  volume = "26",
  year = "1979",
  pages = "17--31",
  keywords = "longest common subsequence, random sequences, limit
results, lower bounds",
  commentnote =  "Summary of Deken thesis (Stanford, 1979). Results are 
1) $L_N / N$ converges a.s. to a constant
2) lower bounds methods for uniform k-ary alphabets
3) asymptotic lower bound of $1/\sqrt{k}$"}

@article{efron-stein,
  author = "B. Efron and C. Stein",
  title = "The Jackknife Estimate of Variance",
  journal = "The Annals of Statistics",
  volume = "9",
  number = "3",
  year = "1981",
  pages = "586--596",
  keywords = "Jackknife, variance estimation, {ANOVA} decompostion,
bootstrap, U-statistics",
  commentnote =  "upward bias of the jacknife estimate"}

@article{erdos-renyi,
  author = "{Erd\H{o}s}, P. and R\'enyi, A.",
  title = "On a New Law of Large Numbers",
  journal = "Journal D'Analyse Math\'ematique",
  volume = "23",
  year = "1970",
  pages = "103--111"}

@inproceedings{erdos-revesz,
  author = "{Erd\H{o}s}, P. and R\'ev\'esz, P.",
  title = "On the Length of the Longest Head-Run",
  booktitle = "Colloquia Mathematica Societatis J\'anos Bolyai, 16.
Topics in Information Theory",
  address = "Keszthely, Hungary",
  year = "1975",
  pages = "219--228"}

@book{feller:I,
  author = "Feller, W.",
  title = "An Introduction to Probability Theory and Its
Applications",
  volume = "I",
  edition = "3rd",
  publisher = "Wiley",
  address = "New York",
  year = "1968"}

@book{feller:II,
  author = "Feller, W.",
  title = "An Introduction to Probability Theory and Its
Applications",
  volume = "II",
  edition = "2nd",
  publisher = "Wiley",
  address = "New York",
  year = "1971"}

@article{frt:hook,
  author = "Frame, J. S. and Robinson, G.  de B. and Thrall, R. M.",
  title = "The Hook Graphs of the Symmetric Group",
  journal = "Canadian Journal of Mathematics",
  volume = "6",
  year = "1954",
  pages = "316--324"}

@article{fredman,
  author = "Fredman, M. L.",
  title = "On Computing the Length of Longest Increasing
Subsequences",
  journal = "Discrete Mathematics",
  volume = "11",
  number = "1",
  year = "1975",
  pages = "29--35"}

@article{gerber-li,
  author = "Gerber, H. U. and Li, S. R.",
  title = "The Occurrence of Sequence Patterns in Repeated
Experiments and Hitting Times in a {M}arkov Chain",
  journal = "Stochastic Processes and their Applications",
  volume = "11",
  year = "1981",
  pages = "101--108",
  commentnote =  "not thesis related"}

@article{gordon,
  author = "Gordon, A. D.",
  title = "{Y}oung Tableaux and Longest Monotone Subsequences:  {A}n
Inequality and a Conjecture",
  year = "1984",
  journal = "Proceedings of the Edinburgh Mathematical Society",
  volume = "27",
  pages = "341--344"}

@article{greene,
  author = "C. Greene",
  title = "An Extension of {S}chensted's Theorem",
  journal = "Advances in Mathematics",
  volume = "14",
  pages = "254--265",
  year = "1974",
  annote = "extends Schensted's theorem to include other rows and columns"}

@article{guibas-odlyzko:1,
  author = "Guibas, L. J. and Odlyzko, A. M.",
  title = "Long Repetitive Patterns in Random Sequences",
  volume = "53",
  year = "1980",
  pages = "241--262",
  journal = "Zeitschrift f{\"u}r Wahrscheinlichkeitstheorie und
verwandte Gebiete"}

@article{guibas-odlyzko:2,
  author = "Guibas, L. J. and Odlyzko, A. M.",
  title = "Periods in Strings",
  journal = "Journal of Combinatorial Theory, Series A",
  volume = "30",
  year = "1981",
  pages = "19--42"}

@article{guibas-odlyzko:3,
  author = "Guibas, L. J. and Odlyzko, A. M.",
  title = "String Overlaps, Pattern Matching, and Nontransitive
Games",
  journal = "Journal of Combinatorial Theory, Series A",
  volume = "30",
  year = "1981",
  pages = "183--208"}

@article{hall-dowling,
  author = "Hall, P. A. V. and Dowling, G. R.",
  title = "Approximate String Matching",
  journal = "Computing Surveys",
  volume = "12",
  number = "4",
  year = "1980",
  pages = "381--402"}

@techreport{hirschberg:1974tr,
  author = "D. S. Hirschberg",
  title = "On Finding Maximal Common Subsequences",
  institution = "Department of Electrical Engineering, Computer Science
Laboratory, Princeton University",
  number = "TR 156",
  year = "1974",
  keywords = "common subsequence, longest common subsequence,
string-to-string edit, algorithms",
  commentnote =  "A simpler version of the later ACM paper.
 Produces two algorithms of time $O(np)$ and $O(p(n-p)ln(n))$ where $p$ is
LCS length"}

@article{hunt-szymanski,
  author = "J. W. Hunt and T. G. Szymanski",
  title = "A Fast Algorithm for Computing Longest Common
Subsequences",
  journal = "Communications of the Association for Computing Machinery",
  volume = "20",
  number = "5",
  year = "1977",
  pages = "350--353",
  keywords = "longest common subsequence, efficient algorithms",
  commentnote =  "UNIX diff algorithm, very good for highly sparse matrix ,
i.e. hash each 
line of data to a single element and get not spurious matches.
Running time is $O((r + n) \ln (n))$, where $r$ is number of matches."}

@article{karlin-ghandour:1,
  author = "S. Karlin and G. Ghandour",
  title = "Comparative Statistics for {DNA} and Protein Sequences:
{S}ingle Sequence Analysis",
  journal = "Proceedings of the National Academy of Sciences USA",
  volume = "82",
  pages = "5800--5804",
  year = "1985"}

@article{karlin-ghandour:2,
  author = "S. Karlin and G. Ghandour",
  title = "Comparative Statistics for {DNA} and Protein Sequences:
{M}ultiple Sequence Analysis",
  journal = "Proceedings of the National Academy of Sciences USA",
  volume = "82",
  pages = "6186--6190",
  year = "1985"}

@article{karlin-rinott,
  author = "S. Karlin and Y. Rinott",
  title = "Applications of {ANOVA} Type Decompositions for Comparisons
of Conditional Variance Statistics Including Jackknife Estimates",
  journal = "The Annals of Statistics",
  volume = "10",
  number = "2",
  year = "1982",
  pages = "485--501",
  keywords = "orthogonal decomposition, jackknife statistics, bias
comparisons, absolute monotonicity, {ANOVA}",
  commentnote =  "Extension of Jackknife estimates of Efron and Stein."}

@article{kingman,
  author = "J. F. C.  Kingman",
  title = "Subadditive Ergodic Theory",
  journal = "The Annals of Probability",
  volume = "1",
  number = "6",
  year = "1973",
  pages = "883--909",
  keywords = "subadditive processes, ergodic theory, percolation
processes, products of",
  keywords = "random matrices, random permutations.",
  commentnote =  "Survey report on the 60's and early 70's work on subadd.
erg. processes."}

@article{steele,
  author = "J. M. Steele",
  title = "Long Common Subsequences and the Proximity of Two Random
Strings",
  journal = "SIAM Journal of Applied Mathematics",
  volume = "42",
  number = "4",
  year = "1982",
  pages = "731--737",
  keywords = "longest common subsequence, variance, Schur convexity,
other comparison",
  keywords = "statistics",
  commentnote =  "results are
1) $O(N)$ variance using Jackknife estimate
2) alternative statistics
3) suggest conjecture that $c(p)$ is Schur convex ( the match
fraction)"}

@article{wagner-fischer,
  author = "R. A. Wagner and M. J. Fischer",
  title = "The String-to-String Correction Problem",
  journal = "Journal of the Association for Computing Machinery",
  volume = "21",
  number = "1",
  year = "1974",
  pages = "168--173",
  keywords = "string correction, editing, string modification,
correction,",
  keywords = "spelling correction, longest common subsequence",
  commentnote =  "Fairly early paper on LCS and related topics. Not
weighty."}

@article{hirschberg:1977,
  author = "D. S. Hirschberg",
  title = "Algorithms for the Longest common Subsequence Problem  ",
  journal = "Journal of the Association for Computing Machinery",
  volume = "24",
  number = "4",
  year = "1977",
  pages = "664--675",
  keywords = "subsequence, common subsequence, algorithm",
  commentnote =  "Two algorithms for the LCS. 
1) $O(pn + n ln(n))$ for LCS of length $p$ (good for very short ones)
2) $O(p(m+1-p)ln(n))$ for very short $m$.
Basically keep a table of next location to search.  "}

@inproceedings{hammersley,
  author = "J. M. Hammersley",
  title = "A Few Seedlings of Research",
  booktitle = "Proceedings, 6th Berkeley Symposium on Mathematics,
Statistics and Probability",
  year = "1972",
  volume = "1",
  pages = "345--394",
  publisher = "University of California Press",
  address = "Berkeley"}

@article{hirschberg,
  author = "D. S. Hirschberg",
  title = "A Linear Space Algorithm for Computing Maximal Common
Subsequences",
  journal = "Communications of the Association for Computing Machinery",
  volume = "18",
  number = "6",
  year = "1975",
  pages = "341--343"}

@article{ivanov-novikov,
  author = "V. A. Ivanov and A. E. Novikov",
  title = "On the Distribution of the Time up to the First Occurrence
of a Given number of Different $\ell$-tuple Series",
  journal = "Theory of Probability and its Applications",
  volume = "22",
  number = "3",
  year = "1977",
  pages = "533--542",
  commentnote = "not directly thesis related"}

@article{kar-ghan-foul-korn,
  author = "Karlin, S. and Ghandour, G. and Foulser, D. E. and Korn, L.J.",
  title = "Comparative Analysis of Human and Bovine Papillomaviruses",
  journal = "Journal of Molecular Biology and Evolution",
  volume = "1",
  number = "4",
  pages = "357--370",
  year = "1984"}

@article{kar-ghan-foul,
  author = "Karlin, S. and Ghandour, G. and Foulser, D. E.",
  title = "{DNA} Sequence Comparisons of the Human, Mouse, and Rabbit
Immunoglobulin Kappa Gene",
  journal = "Journal of Molecular Biology and Evolution",
  volume = "2",
  number = "1",
  pages = "35--52",
  year = "1985"}

@inproceedings{karlin-ost,
  author = "S. Karlin and F. Ost",
  title = "Maximal Segmental Match Length Among Random Sequences from
a Finite Alphabet",
  booktitle = "Proceedings of the Berkeley Conference in Honor of
Jerzy Neyman and Jack Kiefer",
  volume = "1",
  editor = "L. M. Le Cam and R. A. Olshen",
  publisher = "Wadsworth",
  year = "1985",
  pages = "225--243"}

@article{karlin-ost:2,
  author = "S. Karlin and F. Ost",
  title = "Counts of Long Aligned Word Matches Among Random Letter
Sequences",
  journal = "to appear"}

@article{karlin-ost:3,
  author = "S. Karlin and F. Ost",
  title = "Maximal Length of Common Words Among Random Letter
Sequences",
  journal = "to appear"}

@article{karlin-ghandour-ost-tavare-korn,
 author = "S. Karlin and G. Ghandour and F. Ost and S. Tavare and L. J. Korn",
 title = "New Approaches for Computer Analysis of Nucleic Acid Sequences",
  journal = "Proceedings of the National Academy of Sciences USA",
  volume = "80",
  year = "1983",
  pages = "5660--5664"}

@book{knuth:I,
  author = "D. E. Knuth",
  title = "The Art of Computer Programming, Volume 1:  Fundamental
Algorithms",
  publisher = "Addison-Wesley",
  address = "Reading, Massachusetts",
  edition = "2nd",
  year = "1973"}

@book{knuth:III,
  author = "D. E. Knuth",
  title = "The Art of Computer Programming, Volume 3:  Sorting and Searching",
  publisher = "Addison-Wesley",
  address = "Reading, Massachusetts",
  year = "1973"}

@article{knuth-morris-pratt,
  author = "D. E. Knuth and J. H. Morris and V. R. Pratt",
  title = "Fast Pattern Matching in Strings",
  journal = "SIAM Journal of Computing",
  volume = "6",
  year = "1977",
  pages = "323-350"}

@article{kolchin-chistyakov,
  author = "V. F. Kolchin and V. P. Chistyakov",
  title = "Limit Distributions of the number of Non-Occurring
$s$-tuples in a Multinomial Scheme",
  journal = "Theory of Probability and its Applications",
  volume = "19",
  year = "1974",
  pages = "822--830"}

@article{komlos-tusnady,
  author = "J. Koml\'os and G. Tusn\'ady",
  title = "On sequences of ``Pure Heads''",
  journal = "The Annals of Probability",
  volume = "3",
  year = "1975",
  pages = "608--617"}

@article{lamperti,
  author = "J. L. Lamperti",
  title = "A Contribution to Renewal Theory",
  journal = "Proceedings of the American Mathematical Society",
  volume = "12",
  year = "1961",
  pages = "724--731"}

@article{li,
  author = "S. R. Li",
  title = "A Martingale Approach to the Study of Occurrence of
Sequence Patterns in Repeated Events",
  journal = "The Annals of Probability",
  volume = "8",
  number = "6",
  year = "1980",
  pages = "1171--1176",
  commentnote = "not thesis related"}

@article{lifschitz-pittel,
  author = "V. Lifschitz and B. Pittel",
  journal = "Journal of Combinatorial Theory, Series A",
  title = "The Number of Increasing Subsequences of the Random
Permutation",
  volume = "31",
  year = "1981",
  pages = "1--20"}

@article{linial,
  author = "N. Linial",
  title = "A New Derivation of the Counting Formula for {Y}oung
Tableaux",
  journal = "Journal of Combinatorial Theory, Series A",
  volume = "33",
  year = "1982",
  pages = "340--342"}

@article{logan-shepp,
  author = "B. F. Logan and L. A. Shepp",
  title = "A Variational Problem for Random {Y}oung Tableaux",
  journal = "Advances in Mathematics",
  volume = "26",
  year = "1977",
  pages = "206--222"}

@phdthesis{mainville,
  author = "S. Mainville",
  title = "Comparaisons et Autocomparaisons de Cha\^{\i}nes Finies",
  school = "Universit\'e de Montr\'eal",
  year = "1981"}

@incollection{sankoff-mainville,
  author = "Sankoff, D. and Mainville, S.",
  editor = "Sankoff, D. and Kruskal, J. B.",
  title = "Common Subsequences and Monotone Subsequences",
  booktitle = "Time Warps, String Edits, and Macromolecules: The
Theory and Practive of Sequence Comparison",
  publisher = "Addison-Wesley",
  pages = "363--365",
  year = "1983"}

@techreport{masek-paterson,
  author = "W. J. Masek and M. S. Paterson",
  title = "A Faster Algorithm for Computing String-Edit Distances",
  institution = "Massachusetts Institute of Technology",
  year = "1978",
  number = "MIT/LCS/TM-105",
  commentnote = "Time $O(n^{2}/\log n)$ for LCS"}

@article{mikhailov,
  author = "V. G. Mikhailov",
  title = "Limit Distributions of Random Variables Associated with
Multiple Long Duplications in a Sequence of Independent Trials",
  journal = "Theory of Probability and its Applications",
  volume = "19",
  year = "1974",
  pages = "180--184"}

@article{needleman-wunsch,
  author = "S. B. Needleman and C. D. Wunsch",
  title = "A General Method Applicable to the Search for Similarities
in the Amino Acid Sequence of Two Proteins",
  journal = "Journal of Molecular Biology",
  volume = "48",
  year = "1970",
  pages = "443--453"}

@article{okuda-tanaka-kasai,
  author = "T. Okuda and E. Tanaka and T. Kasai",
  title = "A Method for Correction of Garbled Words Based on the
{L}evenshtein Metric",
  journal = "IEEE Transactions on Computers",
  volume = "C25",
  number = "2",
  pages = "172--177",
  year = "1976"}

@unpublished{paterson,
  author = "M. S. Paterson",
  title = "Unpublished Manuscript",
  note = "University of Warwick, England",
  commentnote = "Four Russians method for LCS computation $O(n^{2}/\log n)$",
  year = "1974"}

@inproceedings{revesz,
  author = "P. R\'ev\'esz",
  title = "Strong Theorems on Coin Tossing",
  booktitle = "Proceedings of the 1978 International Congress of
Mathematicians, Helsinki",
  pages = "749--754",
  year = "1980"}

@article{samarova,
  author = "S. S. Samarova",
  title = "On the Length of the Longest Head-Run for a {M}arkov Chain
with Two States",
  journal = "Theory of Probability and its Applications",
  volume = "26",
  number = "3",
  year = "1981",
  pages = "498--509"}

@article{sankoff,
  author = "D.  Sankoff",
  title = "Matching Sequences Under Deletion/Insertion Constraints",
  journal = "Proceedings of the National Academy of Sciences USA",
  volume = "69",
  number = "1",
  pages = "4--6",
  year = "1972"}

@book{sankoff-kruskal,
  editor = "D. Sankoff and J. B. Kruskal",
  title = "Time Warps, String Edits, and Macromolecules:  The Theory
and Practice of Sequence Comparison",
  publisher = "Addison-Wesley",
  address = "Reading, Massachusetts",
  year = "1983"}

@article{schensted,
  author = "C. Schensted",
  title = "Longest Increasing and Decreasing Subsequences",
  journal = "Canadian Journal of Mathematics",
  volume = "13",
  year = "1961",
  pages = "179--191"}

@article{selkow,
  author = "S. M. Selkow",
  title = "The Tree-to-Tree Editing Problem",
  journal = "Information Processing Letters",
  volume = "6",
  number = "6",
  pages = "184--186",
  year = "1977"}

@article{sellers,
  author = "P. H. Sellers",
  title = "An Algorithm for the Distance Between Two Finite Sequences",
  journal = "Journal of Combinatorial Theory, Series A",
  volume = "16",
  number = "2",
  year = "1974",
  pages = "253--258"}

@article{sevastyanov,
  author = "B. A. Sevast'yanov",
  title = "Poisson Limit Law for a Scheme of Sums of Dependent
Random Variables",
  journal = "Theory of Probability and its Applications",
  year = "1972",
  volume = "17",
  number = "4",
  pages = "695--699"}

@article{solovev,
  author = "A. D. Solov'ev",
  title = "A Combinatorial Identity and Its Application to the
Problem Concerning the First Occurrence of a Rare Event",
  journal = "Theory of Probability and its Applications",
  volume = "11",
  pages = "276--282",
  year = "1966"}

@CONFERENCE{van-emde-boas,
  author = "van Emde Boas, P.",
  title = "Preserving Order in a Forest in Less Than Logarithmic Time",
  booktitle = "Proceedings of the 
16th Annual Symposium on the Foundations of Computer Science",
  year = "1975",
  pages = "75--84"}

@article{vershik-kerov,
  author = "A. M. Ver\v{s}ik and S. V. Kerov",
  title = "Asymptotics of the {P}lancherel Measure of the Symmetric
Group and the Limiting Form of {Y}oung Tables",
  journal = "Soviet Mathematics Doklady",
  volume = "18",
  number = "2",
  year = "1977",
  pages = "527--531"}

@article{wong-chandra,
  author = "C. K. Wong and A. K. Chandra",
  title = "Bounds for the String-Editing Problem",
  journal = "Journal of the Association for Computing Machinery",
  year = "1976",
  volume = "23",
  number = "1",
  pages = "13--16"}

@inproceedings{weiner,
  author = "P. Weiner",
  title = "Linear Pattern Matching Algorithms",
  booktitle = "Proceedings of the 14th Annual Symposium on Switching
and Automatic Theory",
  year = "1973",
  pages = "1--11"}

@techreport{yao-yao,
  author = "A. C. Yao and F. F. Yao",
  title = "On Computing the Rank Function for a Set of Vectors",
  institution = "Department of Computer Science, University of
Illinois at Urbana-Champaign",
  number = "UIUCDCS-R-75-699",
  year = "1975"}

@article{zubkov-mikhailov:1,
  author = "A. M. Zubkov and V. G. Mikhailov",
  title = "Limit Distributions of Random Variables Associated with
Long Duplications in a Sequence of Independent Trials",
  journal = "Theory of Probability and its Applications",
  volume = "19",
  pages = "172--179",
  year = "1974"}

@article{zubkov-mikhailov:2,
  author = "A. M. Zubkov and V. G. Mikhailov",
  title = "Repetitions of $s$-tuples in a Sequence of Independent Trials",
  journal = "Theory of Probability and its Applications",
  volume = "24",
  number = "2",
  pages = "269--282",
  year = "1979"}

@incollection{ulam,
  author = "Ulam, S. M.",
  title = "Monte {C}arlo Calculations in Problems of Mathematical Physics",
  booktitle = "Modern Mathematics for the Engineer: Second Series",
  editor = "Beckenbach, E. F.",
  publisher = "Mc{G}raw-{H}ill",
  address = "New York",
  year = "1961"}

@article{vintsyuk,
  author = "Vintsyuk, T. K.",
  title = "Speech Discrimination by Dynamic Programming",
  journal = "Cybernetics",
  volume = "4",
  number = "1",
  pages = "52--57",
  note = "Russian {\it Kibernetika} 4(1):81--88",
  year = "1968"}

@article{velichko-zagoruyko,
  author = "Velichko, V. M. and Zagoruyko, N. G.",
  title = "Automatic Recognition of 200 words.",
  journal = "International Journal of Man--Machine Studies",
  volume = "2",
  pages = "223--234",
  year = "1970"}

@inproceedings{sakoe-chiba:1,
  author = "Sakoe, H. and Chiba, S.",
  title = "A Dynamic-Programming Approach to Continuous Speech Recognition",
  booktitle = "1971 Proceedings of the International Congress of Acoustics,
Budapest, Hungary",
  note = "Paper 20 C 13",
  year = "1971"}

@article{sakoe-chiba:2,
  author = "Sakoe, H. and Chiba, S.",
  title = "Dynamic-Programming Algorithm Optimization for Spoken-Word 
Recognition",
  journal = "IEEE Transactions for Acoustics, Speech, and Signal Processing",
  volume = "ASSP-26",
  pages = "43-49",
  year = "1978"}

@article{reichert-cohen-wong,
  author = "Reichert, T. A. and Cohen, D. N. and Wong, A. K. C.",
  title = "An Application of Information Theory to Genetic Mutations and
the Matching of Polypeptide Sequences",
  journal = "Journal of Theoretical Biology",
  volume = "42",
  pages = "245-261",
  year = "1973"}

@phdthesis{haton:1,
  author = "Haton, J. P.",
  title = "Contribution {\`a} l'analyse, param{\'e}trisation 
et la reconnaissance automatique de la parole",
  school = "Universit{\'e} de Nancy, Nancy, France",
  year = "1973"}

@article{haton:2,
  author = "Haton, J.-P.",
  title = "Une M\'ethode Dynamique de Comparaison de Cha{\^\i}nes 
de Symboles de Longeurs Diff\'erentes: 
{A}pplication \`a la Recherche Lexicale",
  journal = "Comptes Rendus Hebdomadaires des S\'eances de l'Academie des 
Sciences, Serie A",
  volume = "278",
  number = "23",
  pages = "1527--1530",
  year = "1974"}

@article{haton:3,
  author = "Haton, J. P.",
  title = "Practical Application of a Real-Time Isolated-Word
Recognition System Using Syntactic Constraints",
  journal = "IEEE Transactions on Acoustics, Speech, and Signal Processing",
  volume = "ASSP-22",
  number = "6",
  pages = "416--419",
  year = "1974"}

@article{goad-kanehisa,
  author = "Goad, W. B. and Kanehisa, M. I.",
  title = "Pattern Recognition in Nucleic Acid Sequences. {I}. {A}
General Method for Finding Local Homologies and Symmetries",
  journal = "Nucleic Acids Research",
  volume = "10",
  number = "1",
  pages = "247-263",
  year="1982"}

@article{kanehisa-goad,
  author = "Kanehisa, M. I. and Goad, W. B.",
  title = "Pattern Recognition in Nucleic Acid Sequences. {II}. {A}n
Efficient Method for Finding Locally Stable Secondary Structures", 
  journal = "Nucleic Acids Research",
  volume = "10",
  number = "1",
  pages = "265-277",
  year="1982"}

@article{korn-queen-wegman,
  author = "Korn, L. J. and Queen, C. L. and Wegman, M. N.",
  title = "Computer Analysis of Nucleic Acid Regulatory Sequences", 
  journal = "Proceedings of the National Academy of Sciences USA",
  volume = "74",
  number = "10",
  pages = "4401--4405",
  year="1977"}

@article{korn-queen-wegman:2,
  author = "Queen, C. L. and Wegman, M. N. and Korn, L. J.",
  title = "Improvements to a Program for {DNA} Analysis: {A} Procedure to
Find Homologies Among Many Sequences", 
  journal = "Nucleic Acids Research",
  volume = "10",
  number = "1",
  pages = "449-456",
  year="1982"}

@article{sankoff-cedergren,
  author = "Sankoff, D. and Cedergren, R. J.",
  title = "A Test for Nucleotide-Sequence Homology",
  journal = "Journal of Molecular Biology",
  volume = "77",
  pages = "159-164",
  year = "1973"}

@article{dewachter,
  author = "de Wachter, R.",
  title = "The Number of Repeats Expected in Random Nucleic Acid Sequences and
Found in Genes",
  journal = "Journal of Theoretical Biology",
  volume = "91",
  pages = "71--98",
  year = "1981",
  annote = "fixed length repeat probabilities, with examples"}

@article{wilbur-lipman:1983,
  author = "W. J. Wilbur and D. J. Lipman",
  title = "Rapid Similarity Searches of Nucleic Acid and Protein Data Banks",
  journal = "Proceedings of the National Academy of Sciences USA",
  volume = "80",
  pages = "726--730",
  year = "1983",
  annote = "window method of sequence similarity scoring"}

@article{lip-wil-smi-wat,
  author = "Lipman, D. J. and Wilbur, W. J. and Smith, T. F. and 
Waterman, M. S.",
  title = "On the Statistical Significance of Nucleic Acid Similarities",
  journal = "Nucleic Acids Research",
  volume = "12",
  number = "1",
  pages = "215--226",
  year = "1984",
  annote = "removing apparent similarity by adding info to seq. composition
model "}

@article{smith-waterman,
  author = "Smith, T. F. and Waterman, M. S.",
  title = "Identification of Common Molecular Subsequences",
  journal = "Journal of Molecular Biology",
  volume = "147",
  pages = "195--197",
  year = "1981",
  annote = "short--weighted LCS"}

@article{fitch-smith,
  author = "Fitch, W. M. and Smith, T. F.",
  title = "Optimal Sequence Alignments",
  journal = "Proceedings of the National Academy of Sciences USA",
  volume = "80",
  pages = "1382--1386",
  year = "1983",
  annote = "table of LCS scoring regions by variable weight -- useful?"}

@article{lipman-pearson,
  author = "Lipman, D. J. and Pearson, W. R.",
  title = "Rapid and Sensitive Protein Similarity Searches",
  journal = "Science",
  volume = "227",
  pages = "1435--1441",
  year = "1985",
  annote = "several pass method of scoring -- supposed to be fast. Retains
quadratic time behavior with lower constant."}

@article{brutlag-co,
 author = "Brutlag, D. L. and Clayton, J. and Friedland, P. and Kedes, L. H.",
  title = "{SEQ}:{A} Nucleotide Sequence Analysis and Recombination System",
  journal = "Nucleic Acids Research",
  volume = "10",
  pages = "279-294",
  year = "1982",
  annote = ""}

@article{knuth:tableaux,
  author = "Knuth, D. E.",
  title = "Permutations, Matrices, and Generalized {Y}oung Tableaux",
  journal = "Pacific Journal of Mathematics",
  volume = "34",
  number = "3",
  pages = "709--727",
  year = "1970",
  annote = "extends Schensted's results to multi-sets "}

@article{lam,
  author = "Lam, T. Y.",
  title = "Young Diagrams, {S}chur Functions, the {G}ale-{R}yser Theorem and a
Conjecture of {S}napper",
  journal = "Journal of Pure and Applied Algebra",
  volume = "10",
  pages = "81--94",
  year = "1977",
  annote = "not thesis related: very algebraic"}

@article{vo,
  author = "Vo, K.-P. and Whitney, R.",
  title = "Tableaux and Matrix Correspondences",
  journal = "Journal of Combinatorial Theory, Series A",
  volume = "35",
  pages = "328--359",
  year = "1983",
  annote = "not thesis related: platic monoid, Schutzenberger operator"}

@article{fomin,
  author = "Fomin, S. V.",
  title = "Finite Partially Ordered Sets and {Y}oung Tableaux",
  journal = "Soviet Mathematics Doklady",
  volume = "19",
  number = "6",
  pages = "1510--1514",
  year = "1978",
  annote = "not thesis related: chains and anti-chains"}

@article{brutlag-et-al,
  author = "Abarbanel, R. M. and Wienecke, P. R. and Mansfield, E. 
and Jaffe, D. A. and Brutlag, D. L.",
  title = "Rapid Searches for Computer Patterns in Biological Molecules",
  journal = "Nucleic Acids Research",
  volume = "12",
  pages = "263--280",
  year = "1984",
  annote = "check this reference "}

@article{waterman-arratia-galas,
  author = "Waterman, M. S. and Arratia, R. and Galas, D. J.",
  title = "Pattern Recognition in Several Sequences: {C}onsensus and 
Alignment",
  journal = "Bulletin of Mathematical Biology",
  volume = "46",
  number = "4",
  pages = "515--527",
  year = "1984",
  annote = "consensus methods using word neighborhoods"}

@article{waterman-smith-beyer,
  author = "Waterman, M. S. and Smith, T. F. and Beyer, W. A.",
  title = "Some Biological Sequence Metrics",
  journal = "Advances in Mathematics",
  volume = "20",
  pages = "367--387",
  year = "1976",
  annote = "showing that trace/alignment/listings are metrics"}