Linked Life Data

15579244

Source:http://linkedlifedata.com/resource/pubmed/id/15579244

Statements in which the resource exists as a subject.
PredicateObject
rdf:type
lifeskim:mentions
pubmed:issue
4
pubmed:dateCreated
2004-12-6
pubmed:abstractText
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 of maximum total weight such that each tiles satisfies the size bounds. A solution to this problem is important to a number of computational biology applications such as selecting genomic DNA fragments for PCR-based amplicon microarrays and 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 first discuss the solution to 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 the tiling problems introduced. We also discuss NP-hardness results and approximation algorithms for generalizing our basic tiling problem to higher dimensions. Finally, computational results from applying our tiling algorithms to genomic sequences of five model eukaryotes are reported.
pubmed:grant
pubmed:language
eng
pubmed:journal
pubmed:citationSubset
IM
pubmed:chemical
pubmed:status
MEDLINE
pubmed:issn
1066-5277
pubmed:author
pubmed:issnType
Print
pubmed:volume
11
pubmed:owner
NLM
pubmed:authorsComplete
Y
pubmed:pagination
766-85
pubmed:dateRevised
2007-11-14
pubmed:meshHeading
pubmed:year
2004
pubmed:articleTitle
Fast optimal genome tiling with applications to microarray design and homology search.
pubmed:affiliation
Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA 16802, USA.
pubmed:publicationType
Journal Article, Research Support, U.S. Gov't, P.H.S., Research Support, U.S. Gov't, Non-P.H.S., Research Support, Non-U.S. Gov't