Fast algorithms for the density finding problem

DOI10.1007/S00453-007-9023-8MaRDI QIDQ1024779zbMATH OpenOpenAlexFDO

Authors Tien-Ching Lin, Hsueh-I Lu, Der-Tsai Lee

Publication date 17 June 2009

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-9023-8

zbMATH Keywords

computational geometryconvex hullDNA sequencebioinformaticsdensity finding problemGC contentmaximum-density segment problemslope selection problem

Mathematics Subject Classification ID

Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• scientific article; zbMATH DE number 1945161
• Fast and space-efficient location of heavy or dense segments in run-length encoded sequences (extended abstract)
• An Optimal Algorithm for the Maximum-Density Segment Problem
• An optimal algorithm for the maximum-density segment problem
• Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications

Cites work

• scientific article; zbMATH DE number 1945161 (Why is no real title available?)
• An Optimal Algorithm for the Maximum-Density Segment Problem
• An efficient algorithm for determining the convex hull of a finite planar set
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• Introduction to algorithms.
• Linear-time algorithm for finding a maximum-density segment of a sequence
• Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications

Cited in

(13)

• The computational complexity of densest region detection
• Algorithms and Computation
• Algorithms for problems on maximum density segment
• scientific article; zbMATH DE number 1945161 (Why is no real title available?)
• Fast algorithms for finding disjoint subsequences with extremal densities
• Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications
• An optimal algorithm for the maximum-density segment problem
• Optimal randomized algorithm for the density selection problem
• Searching a bitstream in linear time for the longest substring of any given density
• Locating regions in a sequence under density constraints
• An Optimal Algorithm for the Maximum-Density Segment Problem
• Minkowski sum selection and finding
• The density maximization problem in graphs

Describes a project that uses

Uses Software

• MAVG
• EMBOSS

This page was built for publication: Fast algorithms for the density finding problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024779)