Approximate matching of regular expressions

Eugene W. Myers; Webb Miller

doi:10.1007/bf02458834

journal article Jan 01, 1989

Approximate matching of regular expressions

Eugene W. Myers

Webb Miller

Bulletin of Mathematical Biology Vol. 51 No. 1 pp. 5-37 · Springer Science and Business Media LLC

View at Publisher Save 10.1007/bf02458834

Topics

No keywords indexed for this article. Browse by subject →

References

25

[1]

Abarbanel, R. M., P. R. Wieneke, E. Mansfield, D. A. Jaffe and D. L. Brutlag. 1984. “Rapid Searches for Complex Patterns in Biological Molecules.”Nucleic Acids Res. 12, 263–280. 10.1093/nar/12.1part1.263

[2]

Aho, A. 1980. “Pattern Matching in Strings.” InFormal Language Theory, R. Book (Ed.). New York: Academic Press.

[3]

—, J. E. Hopcroft and J. D. Ullman. 1983.Data Structures and Algorithms, pp. 203–208. Reading, MA: Addison-Wesley.

[4]

Turn prediction in proteins using a pattern-matching approach

F. E. Cohen, R. M. Abarbanel, I. D. Kuntz et al.

Biochemistry 1986 10.1021/bi00349a037

[5]

Optimal sequence alignments

Walter M. Fitch, Temple F. Smith

Proceedings of the National Academy of Sciences 1983 10.1073/pnas.80.5.1382

[6]

An improved algorithm for matching biological sequences

Osamu Gotoh

Journal of Molecular Biology 1982 10.1016/0022-2836(82)90398-9

[7]

Hecht, M. S. 1977.Flow Analysis of Computer Programs. Amsterdam: North-Holland.

[8]

— and J. D. Ullman. 1975. “A Simple Algorithm for Global Data Flow Analysis Programs.”SIAM J. Computing 4, 519–532. 10.1137/0204044

[9]

Hopcroft, J. E. and J. D. Ullman. 1979.Introduction to Automata Theory, Languages, and Computation. Reading, MA: Addison-Wesley.

[10]

Kennedy, K. 1975. “Node Listing Techniques Applied to Data Flow Analysis.”Proceedings of the 2nd ACM Conference on Principles of Programming Languages, 10–21.

[11]

Levenshtein, V. I. 1966. “Binary Codes Capable of Correcting Deletions, Insertions, and Reversals.”Cybernetics Control Theory 10, 707–710.

[12]

Miller, W. 1987.A Software Tools Sampler. New Jersey. Prentice-Hall.

[13]

— and E. W. Myers. 1988a. “A Simple Row-Replacement Method.”Software-Practice and Experience 18, 597–611. 10.1002/spe.4380180703

[14]

— and —. 1988b. “Sequence Comparison with Concave Weighting Functions.”Bull. Math. Biol. 50, 97–120. 10.1007/bf02459948

[15]

Myers, E. W. and W. Miller. 1988a. “Row replacement Algorithms for Screen Editors.”ACM Trans. Prog. Lang. Systems. (to be published).

[16]

— and —. 1988b. “Optimal Alignments in Linear Space.”CABIOS 4, 11–17.

[17]

Pennello, T. J. 1986. “Very Fast LR Parsing.” Proceedings of the SIGPLAN'86 Symposium on Compiler Construction.ACM SIGPLAN Notices 21, 145–150. 10.1145/13310.13326

[18]

Sankoff, D. and J. B. Kruskal. 1983.Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison. Reading, MA: Addison-Wesley.

[19]

Sellers, P. H. 1980. “The Theory and Computation of Evolutionary Distances: Pattern Recognition.”J. Algorithms 1, 359–373. 10.1016/0196-6774(80)90016-4

[20]

Pattern recognition in genetic sequences by mismatch density

Peter H. Sellers

Bulletin of Mathematical Biology 1984 10.1007/bf02459499

[21]

Thompson, K. 1968. “Regular Expression Search Algorithm.”Comm. ACM 11, 419–422. 10.1145/363347.363387

[22]

Wagner, R. A. 1974. “Order-n Correction of Regular Languages.”Comm. ACM 17, 265–268. 10.1145/360980.360995

[23]

— and J. I. Seiferas. 1978. “Correcting Counter-Automaton-Recognizable Languages.”SIAM J. Computing 7, 357–375. 10.1137/0207029

[24]

General methods of sequence comparison

Michael S. Waterman

Bulletin of Mathematical Biology 1984 10.1007/bf02459498

[25]

Some biological sequence metrics

M.S Waterman, T.F Smith, W.A Beyer

Advances in Mathematics 1976 10.1016/0001-8708(76)90202-4

Cited By

95

Potential of mean force for protein–protein interaction studies

Lin Jiang, Ying Gao · 2001

Proteins: Structure, Function, and...

Alignments Without Low-Scoring Regions

Zheng Zhang, Piotr Berman · 1998

Journal of Computational Biology

Metrics

95

Citations

25

References

Details

Published: Jan 01, 1989
Vol/Issue: 51(1)
Pages: 5-37
License: View

Authors

E

Eugene W. Myers

Celera Genomics, 45 West Gude Drive, Rockville, MD 20850, USA.

W

Webb Miller

Cite This Article

Eugene W. Myers, Webb Miller (1989). Approximate matching of regular expressions. Bulletin of Mathematical Biology, 51(1), 5-37. https://doi.org/10.1007/bf02458834

Approximate matching of regular expressions

You May Also Like