Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications

DOI10.1016/j.jcss.2004.08.001zbMath1088.68177arXivcs/0207026OpenAlexW2086065942MaRDI QIDQ1776373

Ming-Yang Kao, Michael H. Goldwasser, Hsueh-I Lu

Publication date: 12 May 2005

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0207026

zbMATH Keywords

sequencesdensitybioinformatics

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Biochemistry, molecular biology (92C40) Computational methods for problems pertaining to biology (92-08)

Related Items (16)

Finding a maximum-density path in a tree under the weight and length constraints ⋮ Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics ⋮ The density maximization problem in graphs ⋮ Calculating a linear-time solution to the densest-segment problem ⋮ Searching a bitstream in linear time for the longest substring of any given density ⋮ Finding long and similar parts of trajectories ⋮ Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths ⋮ Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence ⋮ An improved algorithm for finding a length-constrained maximum-density subtree in a tree ⋮ An optimal algorithm for the maximum-density path in a tree ⋮ Algorithms for Problems on Maximum Density Segment ⋮ MINKOWSKI SUM SELECTION AND FINDING ⋮ On locating disjoint segments with maximum sum of densities ⋮ Fast algorithms for the density finding problem ⋮ Constrained Minkowski sums: A geometric framework for solving interval problems in computational biology efficiently ⋮ Optimal algorithms for locating the longest and shortest segments satisfying a sum or an average constraint

Cites Work

• Unnamed Item
• Linear-time algorithm for finding a maximum-density segment of a sequence
• Pattern recognition in genetic sequences by mismatch density
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• Fast and Space-Efficient Location of Heavy or Dense Segments in Run-Length Encoded Sequences
• Algorithms - ESA 2003

This page was built for publication: Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications