Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-27T02:13:19.548Z Has data issue: false hasContentIssue false
  • English
  • Français

DNA Sequence Alignment and Critical Phenomena

Published online by Cambridge University Press:  10 February 2011

Dirk Drasdo ,
Terence Hwa  and
Michael Lässig
Dirk Drasdo
Affiliation:
Max-Planck Institut für Kolloid- und Grenzflächenforschung, 14513 Teltow, Germany
Terence Hwa
Affiliation:
Department of Physics, University of California at San Diego, La Jolla, CA 92093–0319
Michael Lässig
Affiliation:
Max-Planck Institut für Kolloid- und Grenzflächenforschung, 14513 Teltow, Germany
Get access

Abstract

Alignment algorithms are commonly used to detect and quantify similarities between DNA sequences. We study these algorithms in the framework of a recent theory viewing similarity detection as a geometrical critical phenomenon of directed random walks. We show that the roughness of these random walks governs the fidelity of an alignment, i.e., its ability to capture the correlations between the sequences compared. Criteria for the optimization of alignment algorithms emerge from this theory.

Type
Research Article
Information
MRS Online Proceedings Library (OPL) , Volume 463: Symposia EE – Statistical Mechanics in Physics and Biology , 1996 , 75
Copyright
Copyright © Materials Research Society 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] See review articles in Met. Enz. 183, (1990).Google Scholar
[2] Needleman, S.B. and Wunsch, C.D., J. Mol. Biol, 48, 444 (1970).Google Scholar
[3] Smith, T.F. and Waterman, M.S., Adv. Appl. Math. 2, 482 (1981).Google Scholar
[4] For a survey of recent developments, see Waterman, M.S., in Mathematical Methods for DNA Sequences, Waterman, M.S. ed., CRC Press (1989); andGoogle Scholar
Waterman, M.S., Introduction to Computational Biology, Chapman & Hall (1994).Google Scholar
[5] Benner, S.A., Cohen, M.A. and Gönnet, G.H., J. Mol. Biol. 229, 1065 (1993).Google Scholar
[6] Vingron, M. and Waterman, M.S., J. Mol. Biol 235, 1 (1994).Google Scholar
[7] Hwa, T. and Lässig, M., Phys. Rev. Lett. 76, 2591 (1996).Google Scholar
[8] Zhang, M.Q. and Marr, T.G., J. Theo. Biol. 174, 119 (1995).Google Scholar
[9] Drasdo, D., Hwa, T., and Lässig, M., Optimal Detection of Similarities in DNA Sequences, preprint (1997).Google Scholar
[10] Bishop, M.J. and Thompson, E.A., J. Mol. Biol. 190, 159 (1986).Google Scholar
[11] Thorne, J.L., Kishino, H., and Felsenstein, J., J. Mol. Evol. 33, 114 (1991).Google Scholar
[12] Kardar, M., Nucl. Phys. B 290, 582 (1987).Google Scholar
[13] Hwa, T. and Fisher, D.S. Phys. Rev. B 49, 3136 (1994).Google Scholar
[14] Hwa, T. and Nattermann, T., Phys. Rev. B 51, 455 (1995).Google Scholar
[15] Kinzelbach, H. and Lässig, M., J. Phys. A 28, 6535 (1995).Google Scholar