This Article Full Text (PDF) All Versions of this Article: gr.4452906v1 16/2/271    most recent Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Bertone, P. Articles by Gerstein, M. Search for Related Content PubMed PubMed Citation Articles by Bertone, P. Articles by Gerstein, M. Social Bookmarking                   What's this?

Methods

Design optimization methods for genomic DNA tiling arrays

¹ Department of Molecular, Cellular, and Developmental Biology, Yale University, New Haven, Connecticut 06520, USA , ² Department of Computer Science, Yale University, New Haven, Connecticut 06520, USA , ³ Department of Molecular Biophysics and Biochemistry, Yale University, New Haven, Connecticut 06520, USA , ⁴ Department of Computer Science, Northwestern University, Evanston, Illinois 60201, USA

A recent development in microarray research entails the unbiased coverage, or tiling, of genomic DNA for the large-scale identification of transcribed sequences and regulatory elements. A central issue in designing tiling arrays is that of arriving at a single-copy tile path, as significant sequence cross-hybridization can result from the presence of non-unique probes on the array. Due to the fragmentation of genomic DNA caused by the widespread distribution of repetitive elements, the problem of obtaining adequate sequence coverage increases with the sizes of subsequence tiles that are to be included in the design. This becomes increasingly problematic when considering complex eukaryotic genomes that contain many thousands of interspersed repeats. The general problem of sequence tiling can be framed as finding an optimal partitioning of non-repetitive subsequences over a prescribed range of tile sizes, on a DNA sequence comprising repetitive and non-repetitive regions. Exact solutions to the tiling problem become computationally infeasible when applied to large genomes, but successive optimizations are developed that allow their practical implementation. These include an efficient method for determining the degree of similarity of many oligonucleotide sequences over large genomes, and two algorithms for finding an optimal tile path composed of longer sequence tiles. The first algorithm, a dynamic programming approach, finds an optimal tiling in linear time and space; the second applies a heuristic search to reduce the space complexity to a constant requirement. A Web resource has also been developed, accessible at http://tiling.gersteinlab.org, to generate optimal tile paths from user-provided DNA sequences.

⁵ Corresponding author.
E-mail mark.gerstein{at}yale.edu; fax (360) 838-7861.

CiteULike    Connotea    Del.icio.us    Digg    Reddit    Technorati    What's this?

This article has been cited by other articles:

				H. He, J. Wang, T. Liu, X. S. Liu, T. Li, Y. Wang, Z. Qian, H. Zheng, X. Zhu, T. Wu, et al. Mapping the C. elegans noncoding transcriptome with a whole-genome tiling microarray Genome Res., October 1, 2007; 17(10): 1471 - 1477. [Abstract] [Full Text] [PDF]

				E. Rivals, A. Boureux, M. Lejeune, F. Ottones, O. Pecharroman Perez, J. Tarhio, F. Pierrat, F. Ruffle, T. Commes, and J. Marti Transcriptome annotation using tandem SAGE tags Nucleic Acids Res., September 27, 2007; 35(17): e108 - e108. [Abstract] [Full Text] [PDF]

				S. Graf, F. G. G. Nielsen, S. Kurtz, M. A. Huynen, E. Birney, H. Stunnenberg, and P. Flicek Optimized design and assessment of whole genome tiling arrays Bioinformatics, July 1, 2007; 23(13): i195 - i204. [Abstract] [Full Text] [PDF]

				G. M. Euskirchen, J. S. Rozowsky, C.-L. Wei, W. H. Lee, Z. D. Zhang, S. Hartman, O. Emanuelsson, V. Stolc, S. Weissman, M. B. Gerstein, et al. Mapping of transcription factor binding regions in mammalian cells by ChIP: Comparison of array- and sequencing-based technologies Genome Res., June 1, 2007; 17(6): 898 - 909. [Abstract] [Full Text] [PDF]

				O. Emanuelsson, U. Nagalakshmi, D. Zheng, J. S. Rozowsky, A. E. Urban, J. Du, Z. Lian, V. Stolc, S. Weissman, M. Snyder, et al. Assessing the performance of different high-density tiling microarray strategies for mapping transcribed regions of the human genome Genome Res., June 1, 2007; 17(6): 886 - 897. [Abstract] [Full Text] [PDF]

				E. Ryder, R. Jackson, A. Ferguson-Smith, and S. Russell MAMMOT--a set of tools for the design, management and visualization of genomic tiling arrays Bioinformatics, April 1, 2006; 22(7): 883 - 884. [Abstract] [Full Text] [PDF]