Fast optimal genome tiling with applications to microarray design and homology search

Piotr Berman, Paul Bertone, Bhaskar DasGupta, Mark Gerstein, Ming-Yang Kao, Michael Snyder

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

In this paper we consider several variations of the following basic tiling problem: given a sequence of real numbers with two size bound parameters, we want to find a set of tiles such that they satisfy the size bounds and the total weight of the tiles is maximized. This solution to this problem is important to a number of computational biology applications, such as selecting genomic DNA fragments for amplicon microarrays, or performing homology searches with long sequence queries. Our goal is to design efficient algorithms with linear or near-linear time and space in the normal range of parameter values for these problems. For this purpose, we discuss the solution of a basic online interval maximum problem via a sliding window approach and show how to use this solution in a nontrivial manner for many of our tiling problems. We also discuss NPhardness and approximation algorithms for generalization of our basic tiling problem to higher dimensions.

Original languageEnglish (US)
Title of host publicationAlgorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings
EditorsRoderic Guigo, Dan Gusfield
PublisherSpringer Verlag
Pages419-433
Number of pages15
ISBN (Print)3540442111, 9783540442110
StatePublished - Jan 1 2002
Event2nd International Workshop on Algorithms in Bioinformatics, WABI 2002 - Rome, Italy
Duration: Sep 17 2002Sep 21 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2452
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd International Workshop on Algorithms in Bioinformatics, WABI 2002
CountryItaly
CityRome
Period9/17/029/21/02

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Berman, P., Bertone, P., DasGupta, B., Gerstein, M., Kao, M-Y., & Snyder, M. (2002). Fast optimal genome tiling with applications to microarray design and homology search. In R. Guigo, & D. Gusfield (Eds.), Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings (pp. 419-433). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2452). Springer Verlag.