Optimal detection of sequence similarity by local alignment

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal detection of sequence similarity by local alignment

Full text

Pdf (1.07 MB)

Source

Annual Conference on Research in Computational Molecular Biology archive
Proceedings of the second annual international conference on Computational molecular biology table of contents

New York, New York, United States

Pages: 109 - 116

Year of Publication: 1998

ISBN:0-89791-976-9

Authors

Terence Hwa	Department of Physics, University of California at San Diego, 9500 Gilman Drive, La Jolla, CA
Michael Lässig	Max-Planck Institut für Kolloid und Grenzflächenforschung, Kantstr. 55, 14513 Teltow, Germany

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 26, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/279069.279103 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Altschul, S.F., Gish, W., Miller, W., Myers, E.W., and Lipman, D.J. Basic local alignment search tool. J. Mol. Biol. 215, 403-410, (1990).
	2	Altschul, S.F. A protein alignment scoring system sensitive at all evolutionary distances. J. Mol. Evol. 36 290-300, (199S).
	3	Altschul, S.F. and Gish, W. Local alignment statistics. Methods in Enzymology 266, 460-480, (1996).
	4	Arratia, tL, Morris, P., and Waterman, M.S. Stochastic scrabbles: a law of large numbers for sequence matching with scores. J. Appl. Probab., 25 106-119, (1988).
	5	Arratia, tL and Waterman, M.S. A phase transition for the score in matching random sequences allowing deletions. Ann. Appl. Prob. 4, 200-225, (1994).
	6	Benner, S.A., Cohen, M.A. and Gonnet, G.H. Empirical and structural models for insertions and deletions in the divergent evolution of proteins. J. Mol. Biol. 229, 1065-1082, (1993).
	7	Collins, J.F., Coulson, A.F.W., and Lye, A. The significance of protein sequence similarities. Comput. Appl. Biosci. 4, 67-71, (1988).
	8	Cule, D. and Hwa, T. Static and Dynamic Properties of ~~homogeneous Elastic Media on Disordered Substrate. Phys. Rev. B. in press.
	9	Domb, C. and Lebowitz, 3.L. Phase Transition and Critical Phenomena. Academic Press, London.
	10	Doolittle, tLF. Methods in Enzymology 266. Academic Press, San Diego, (1996).
	11	Drasdo, D., Hwa, T. and Lissig, M. DNA sequence alignment and critical phenomena. Mat. Rex Soc. Syrup. Proc. 263, 75-80, (1997); and to be published.
	12	Forster, D., Nelson, D.tL, and Stephen, M.3. Largedistance and long-time properties of a randomly stirred fluid. Phys. Rev. A 16, 732-749, (1977).
	13	Gotoh, O. An improved algorithm for matching biological sequences. J. Mol. Biol. 162, 705.708, (1982).
	14	D. Gusfield , K. Balasubramanian , D. Naor, Parametric optimization of sequence alignment, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.432-439, September 1992, Orlando, Florida, United States
	15	Halpin-Healy, T. and Zhang, Y.-C. Kinetic roughening phenomena, stochastic growth, directed polymers and all that: aspects of multidisciplinary statistical mechanics. Phy. Rep. 254, 215414, (1995).
	16	Hwa T. and Fisher, D.S. Anomalous fluctuations of directed polymers in random media. Phys. Rev. B 49, 3136-3154, (1994).
	17	Hwa, T. and Nattexmann, T. Disorder-induced depinning transition. Phys. Rev. B 51, 455-469, (1995).
	18	Hwa, T. and L~ssig, M. SimUari~y detection and localization. Phys. Rev. Left. 76, 2591-2594, (1996).
	19	Kardar, M. Replica Bethe ansatz studies of two-dimensional interfaces with quenched random impurities. Nucl. Phys. B 290, 582-602, (1987).
	20	Kardar, M., Parisi, G., and Zhang, Y.-C. Dynamic scaling of growing interfaces. Phys. Rev. Lett. 56, 889-892, (1986).
	21	Karlin S. and Altschul, S.F. Methods for assessing the statistical significance of molecular sequence featxtres by using general scoring schemes. Proc. Natl. Acad. Sci. U.S.A. 87, 2264-2268, (1990).
	22	Karlin S. and Altschul, S.F. Applications and statistics for multiple high-scoring segments in molecular sequences. Proc. Natl. Acad. Sci. U.S.A. 90, 5873- 5877, (1993).
	23	Kinzelbach, H. and L~ssig, M. Depinning in a random medium. J. Phys. A 28, 6535-6541, (1995).
	24	Krug, J. and Spohn, H., in Solids far from equilibrium: Growth, Morphology, and Defects, C. Godreche ed. Cambridge University Press, (1991).
	25	Mort, tLF. Maxim-m likelihood estimation of the statistical distribution of Smith-Waterman local sequence similarities. Bull. Math. Biol. 54, 59, (1992).
	26	Mufioz, M.A. and Hwa, T. On nonlinear diffusion with muitiplicative noise. Euro. Phys. Left. in press.
	27	Needleman, S.B. and Wunsch, C.D. A general method applicable to the search for similarities in the amino acid sequences of two proteins. J. Mol. Biol., 48, 443- 453, (1970).
	28	Onuchic, J.N, Luthey-Schulten, Z., and Wolynes, P.G. Theory of protein folding: the energy landscape perspective. Annu. Rev. Phys. Chem., 48, 545-600 (1997).
	29	Pearson, W.tL Searching protein sequence libraries: comparison of the sensitivi~ and selectivity of the Smith-Waterman and FASTA algorithms. Genomics lX, 635-650, (1991).
	30	Smith, T.F. and Waterman, M.S. Identification of common molecular subsequences. J. Mol. Biol., 147, 195- 197, (1981).
	31	Smith, T.F., BurLs, C., and Waterman, M.S. The statistical distribution of nucleic acid similarities. Nucl Acids Res. 13, 645-656, (1985).
	32	Vingron, M. and Waterman, M.S. Sequence alignment and penalty choice. Review of concepts, case studies and implications. J. Mol. Bio1235, 1-12, (1994).
	33	Vingron, M. Near-optimal sequence alignment. Gurr. Op. Struct. Biol., 6, 346-352, (1996).
	34	Waterman, M.S., Gordon, L., and Arratia, R. Phase transitions in sequence matches and nucleic acid structure. Proc. Natl. Acad. Sci. br.S.A. 84, 1239-1243, (1987).
	35	Michael S. Waterman, Mathematical Methods for DNA Sequences, CRC Press, Inc., Boca Raton, FL, 1989
	36	Waterman, M.S., Eggert M., and Lander, E. Parametric sequence comparisons. Proc. Natl. Acad. Scic. U.S.A. 89, 6090-6093, (1992).
	37	M.S. Waterman, Introduction to Computational Biology, Chapman & Hall, (1994).
	38	Waterman, M.S. Parametric and ensemble sequence alignment algorithms. Bull. Math. Biol. 56, 743-767, (1994).
	39	Waterman, M.S., and Vingron, M. Rapid and accurate estimates of statistical significance for sequence data base searches. Proc. Natl. Acad. Sci. U.S.A. 91, 4625.4628, (1994).
	40	Waterman, M.S. and Vingron, M. Sequence Comparison significance and Poisson approximation. Star. Sci. 9, 367-381, (1994:).