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

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

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

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

sequences; density; bioinformatics

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

92C40: Biochemistry, molecular biology

92-08: Computational methods for problems pertaining to biology

Related Items

Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics, 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, 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, Finding a maximum-density path in a tree under the weight and length constraints

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