Abstract

A method for string alignment is presented in which a moiré technique is applied to one-dimensional spatial encoding patterns. String alignment, an essential operation in genome analysis, evaluates local similarity between sequences of bases or amino acids. The method uses a simple procedure to provide matching results for not only the same locus but also neighboring loci. Experimental verification shows the effectiveness of the proposed method.

© 1999 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. Optical Society of America, Optics in Computing, Technical Digest (Optical Society of America, Washington, D.C., 1999).
  2. K. Lear, A. Mar, K. D. Choquette, S. P. Kilcoyne, R. P. Schneider, and K. M. Geib, Electron. Lett. 31, 886 (1996).
  3. O. Bryngdahl, J. Opt. Soc. Am. 64, 1287 (1974).
  4. J. Tanida and Y. Ichioka, Int. J. Opt. Comput. 1, 113 (1990).
  5. J. Meidanis, J. C. Setabal, and J. C. Setubal, Introduction to Computational Biology (PWS-Kent, Boston, Mass., 1996).
  6. R. Lewin, Patterns in Evolution—The New Molecular View (Freeman, New York, 1997).
  7. B. Alberts, D. Bray, A. Johnson, J. Lewis, M. Raff, K. Roberts, and P. Walter, Essential Cell Biology (Garland, New York, 1998).
  8. S. B. Needleman and C. D. Wunsch, J. Mol. Biol. 48, 443 (1970).
    [CrossRef] [PubMed]
  9. T. F. Smith and M. F. Waterman, J. Mol. Biol. 147, 195 (1981).
    [CrossRef] [PubMed]
  10. C. M. Fraser and et al., Science 270, 397 (1995).
    [CrossRef] [PubMed]

1996 (1)

K. Lear, A. Mar, K. D. Choquette, S. P. Kilcoyne, R. P. Schneider, and K. M. Geib, Electron. Lett. 31, 886 (1996).

1995 (1)

C. M. Fraser and et al., Science 270, 397 (1995).
[CrossRef] [PubMed]

1990 (1)

J. Tanida and Y. Ichioka, Int. J. Opt. Comput. 1, 113 (1990).

1981 (1)

T. F. Smith and M. F. Waterman, J. Mol. Biol. 147, 195 (1981).
[CrossRef] [PubMed]

1974 (1)

1970 (1)

S. B. Needleman and C. D. Wunsch, J. Mol. Biol. 48, 443 (1970).
[CrossRef] [PubMed]

Alberts, B.

B. Alberts, D. Bray, A. Johnson, J. Lewis, M. Raff, K. Roberts, and P. Walter, Essential Cell Biology (Garland, New York, 1998).

Bray, D.

B. Alberts, D. Bray, A. Johnson, J. Lewis, M. Raff, K. Roberts, and P. Walter, Essential Cell Biology (Garland, New York, 1998).

Bryngdahl, O.

Choquette, K. D.

K. Lear, A. Mar, K. D. Choquette, S. P. Kilcoyne, R. P. Schneider, and K. M. Geib, Electron. Lett. 31, 886 (1996).

Fraser, C. M.

C. M. Fraser and et al., Science 270, 397 (1995).
[CrossRef] [PubMed]

Geib, K. M.

K. Lear, A. Mar, K. D. Choquette, S. P. Kilcoyne, R. P. Schneider, and K. M. Geib, Electron. Lett. 31, 886 (1996).

Ichioka, Y.

J. Tanida and Y. Ichioka, Int. J. Opt. Comput. 1, 113 (1990).

Johnson, A.

B. Alberts, D. Bray, A. Johnson, J. Lewis, M. Raff, K. Roberts, and P. Walter, Essential Cell Biology (Garland, New York, 1998).

Kilcoyne, S. P.

K. Lear, A. Mar, K. D. Choquette, S. P. Kilcoyne, R. P. Schneider, and K. M. Geib, Electron. Lett. 31, 886 (1996).

Lear, K.

K. Lear, A. Mar, K. D. Choquette, S. P. Kilcoyne, R. P. Schneider, and K. M. Geib, Electron. Lett. 31, 886 (1996).

Lewin, R.

R. Lewin, Patterns in Evolution—The New Molecular View (Freeman, New York, 1997).

Lewis, J.

B. Alberts, D. Bray, A. Johnson, J. Lewis, M. Raff, K. Roberts, and P. Walter, Essential Cell Biology (Garland, New York, 1998).

Mar, A.

K. Lear, A. Mar, K. D. Choquette, S. P. Kilcoyne, R. P. Schneider, and K. M. Geib, Electron. Lett. 31, 886 (1996).

Meidanis, J.

J. Meidanis, J. C. Setabal, and J. C. Setubal, Introduction to Computational Biology (PWS-Kent, Boston, Mass., 1996).

Needleman, S. B.

S. B. Needleman and C. D. Wunsch, J. Mol. Biol. 48, 443 (1970).
[CrossRef] [PubMed]

Raff, M.

B. Alberts, D. Bray, A. Johnson, J. Lewis, M. Raff, K. Roberts, and P. Walter, Essential Cell Biology (Garland, New York, 1998).

Roberts, K.

B. Alberts, D. Bray, A. Johnson, J. Lewis, M. Raff, K. Roberts, and P. Walter, Essential Cell Biology (Garland, New York, 1998).

Schneider, R. P.

K. Lear, A. Mar, K. D. Choquette, S. P. Kilcoyne, R. P. Schneider, and K. M. Geib, Electron. Lett. 31, 886 (1996).

Setabal, J. C.

J. Meidanis, J. C. Setabal, and J. C. Setubal, Introduction to Computational Biology (PWS-Kent, Boston, Mass., 1996).

Setubal, J. C.

J. Meidanis, J. C. Setabal, and J. C. Setubal, Introduction to Computational Biology (PWS-Kent, Boston, Mass., 1996).

Smith, T. F.

T. F. Smith and M. F. Waterman, J. Mol. Biol. 147, 195 (1981).
[CrossRef] [PubMed]

Tanida, J.

J. Tanida and Y. Ichioka, Int. J. Opt. Comput. 1, 113 (1990).

Walter, P.

B. Alberts, D. Bray, A. Johnson, J. Lewis, M. Raff, K. Roberts, and P. Walter, Essential Cell Biology (Garland, New York, 1998).

Waterman, M. F.

T. F. Smith and M. F. Waterman, J. Mol. Biol. 147, 195 (1981).
[CrossRef] [PubMed]

Wunsch, C. D.

S. B. Needleman and C. D. Wunsch, J. Mol. Biol. 48, 443 (1970).
[CrossRef] [PubMed]

Electron. Lett. (1)

K. Lear, A. Mar, K. D. Choquette, S. P. Kilcoyne, R. P. Schneider, and K. M. Geib, Electron. Lett. 31, 886 (1996).

Int. J. Opt. Comput. (1)

J. Tanida and Y. Ichioka, Int. J. Opt. Comput. 1, 113 (1990).

J. Mol. Biol. (2)

S. B. Needleman and C. D. Wunsch, J. Mol. Biol. 48, 443 (1970).
[CrossRef] [PubMed]

T. F. Smith and M. F. Waterman, J. Mol. Biol. 147, 195 (1981).
[CrossRef] [PubMed]

J. Opt. Soc. Am. (1)

Science (1)

C. M. Fraser and et al., Science 270, 397 (1995).
[CrossRef] [PubMed]

Other (4)

Optical Society of America, Optics in Computing, Technical Digest (Optical Society of America, Washington, D.C., 1999).

J. Meidanis, J. C. Setabal, and J. C. Setubal, Introduction to Computational Biology (PWS-Kent, Boston, Mass., 1996).

R. Lewin, Patterns in Evolution—The New Molecular View (Freeman, New York, 1997).

B. Alberts, D. Bray, A. Johnson, J. Lewis, M. Raff, K. Roberts, and P. Walter, Essential Cell Biology (Garland, New York, 1998).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (7)

Fig. 1
Fig. 1

String alignment of two DNA sequences.

Fig. 2
Fig. 2

Processing procedure of the proposed method.

Fig. 3
Fig. 3

Coding patterns for DNA bases.

Fig. 4
Fig. 4

String data for experimental alignment.

Fig. 5
Fig. 5

Output patterns obtained by evaluation on (a) S1 and S1 and (b) S1 and S2.

Fig. 6
Fig. 6

Modified output pattern obtained with the lateral shift of one image.

Fig. 7
Fig. 7

Simplified model of the moiré structure.

Equations (4)

Equations on this page are rendered with MathJax. Learn more.

x=d2 sinα/2,
y=d2 cosα/2,
S=2xy=d2/sin α.
P=LMd2/S=LM sin α

Metrics