"2002" .
_:N23e1ec6a915440c295abb9ad3bd9778c .
"chapter" .
"set" .
"algorithm" .
"Department of Computer Science & Engineering, Pennsylvania State University, 16802, University Park, PA, USA" .
_:N8e5eccb9792f4f9ba35459e6e35a3cc7 .
"worst-case performance ratio" .
"alignment" .
"129-138" .
"dimensions" .
.
.
"chapters" .
"two-phase technique" .
_:N976cfdb405f44cad8f8058c3d7f5a6fe .
_:N00ebe6a01c5641a99870ad314af993c3 .
"performance ratio" .
_:N976cfdb405f44cad8f8058c3d7f5a6fe "doi" .
"d dimensions" .
"ratio" .
"axis-parallel rectangles" .
.
.
.
_:Ne896e81f86614506bf4612f2198f9a7b .
_:N3cef58f7615c4aef8359d2ec56564226 _:N061eb7f79b0a4b0993dae5d6fe7f187b .
.
"We consider the following problem motivated by applications to nonoverlapping local alignment problems in computational molecular biology: we are a given a set of n positively weighted axis parallel rectangles such that, for each axis, the projection of a rectangle on this axis does not enclose that of another, and our goal is to select a subset of independent rectangles from the given set of rectangles of total maximum weight, where two rectangles are independent provided for each axis, the projection of one rectangle does not overlap that of another. We use the two-phase technique of [3] to provide a simple approximation algorithm for this problem that runs in O(n log n) time with a worst-case performance ratio of 3. We also discuss extension and analysis of the algorithm in d dimensions." .
_:N23e1ec6a915440c295abb9ad3bd9778c .
"Department of Computer Science, Rutgers University, 08102, Camden, NJ, USA" .
"technique" .
"https://scigraph.springernature.com/explorer/license/" .
"projections" .
"2002-01-01" .
"analysis" .
"Piotr" .
_:Ne896e81f86614506bf4612f2198f9a7b "pub.1014062514" .
_:N061eb7f79b0a4b0993dae5d6fe7f187b .
.
_:N00ebe6a01c5641a99870ad314af993c3 .
"Bhaskar" .
"Berman" .
.
"goal" .
_:Nf9a2f10d058d483d8559353238f20b84 "978-1-4613-7965-2" .
"weight" .
_:N6f4672f1018241f99e57aa130404ff68 "Jose" .
"rectangle" .
"approximation algorithm" .
_:Nf9a2f10d058d483d8559353238f20b84 .
"applications" .
_:Neef8461136a04b48a54e6a9b86cb67df .
"maximum weight" .
.
"time" .
_:Nf9a2f10d058d483d8559353238f20b84 "978-1-4613-0259-9" .
"computational molecular biology" .
"https://doi.org/10.1007/978-1-4613-0259-9_7" .
.
_:Nda90e92f36234584bb9c8d0042e6814e "Pardalos" .
"local alignment problem" .
_:N8e5eccb9792f4f9ba35459e6e35a3cc7 _:N23e1ec6a915440c295abb9ad3bd9778c .
_:N6f4672f1018241f99e57aa130404ff68 "Principe" .
"Numerical and Computational Mathematics" .
_:Nf9a2f10d058d483d8559353238f20b84 .
"problem" .
"local alignment" .
_:N00ebe6a01c5641a99870ad314af993c3 "Springer Nature - SN SciGraph project" .
.
.
"Department of Computer Science, Rutgers University, 08102, Camden, NJ, USA" .
"2022-10-01T07:01" .
.
_:N061eb7f79b0a4b0993dae5d6fe7f187b _:N6f4672f1018241f99e57aa130404ff68 .
"false"^^ .
.
.
_:N6f4672f1018241f99e57aa130404ff68 .
_:Neef8461136a04b48a54e6a9b86cb67df .
"Mathematical Sciences" .
_:N3cef58f7615c4aef8359d2ec56564226 _:Nda90e92f36234584bb9c8d0042e6814e .
"A Simple Approximation Algorithm for Nonoverlapping Local Alignments (Weighted Independent Sets of Axis Parallel Rectangles)" .
_:Nf9a2f10d058d483d8559353238f20b84 "Biocomputing" .
"extension" .
"set of rectangles" .
_:Ne896e81f86614506bf4612f2198f9a7b .
.
"axis" .
"Department of Computer Science & Engineering, Pennsylvania State University, 16802, University Park, PA, USA" .
_:N3cef58f7615c4aef8359d2ec56564226 .
_:N8e5eccb9792f4f9ba35459e6e35a3cc7 .
"parallel rectangles" .
.
_:Ne896e81f86614506bf4612f2198f9a7b "dimensions_id" .
_:Nda90e92f36234584bb9c8d0042e6814e .
"alignment problem" .
_:N976cfdb405f44cad8f8058c3d7f5a6fe .
_:N976cfdb405f44cad8f8058c3d7f5a6fe "10.1007/978-1-4613-0259-9_7" .
_:Nda90e92f36234584bb9c8d0042e6814e "Panos M." .
.
"molecular biology" .
_:Neef8461136a04b48a54e6a9b86cb67df "Springer Nature" .
"simple approximation algorithm" .
"subset" .
"DasGupta" .
"biology" .