Efficient algorithms for consensus string problems minimizing both distance sum and radius

DOI10.1016/j.tcs.2011.05.034zbMath1222.68417OpenAlexW1996705385MaRDI QIDQ719265

Joong Chae Na, Heejin Park, Jeong Seop Sim, Amihood Amir, Gad M. Landau, Kun Soo Park

Publication date: 10 October 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.034

zbMATH Keywords

radiusmultiple alignmentsconsensus stringsdistance sum

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items (7)

Unnamed Item ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Consensus String Problem for Multiple Regular Languages ⋮ Closest substring problems for regular languages ⋮ Consensus string problem for multiple regular languages ⋮ Unnamed Item ⋮ Consensus strings with small maximum distance and small distance sum

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On covering problems of codes
• Approximation algorithms for Hamming clustering problems
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Finding similar regions in many strings
• Optimal Solutions for the Closest-String Problem via Integer Programming
• On the closest string and substring problems
• Trees, Stars, and Multiple Biological Sequence Alignment
• Complexities of the Centre and Median String Problems
• Algorithms on Strings, Trees and Sequences
• A linear-time algorithm for the 1-mismatch problem
• Mapping the genome

This page was built for publication: Efficient algorithms for consensus string problems minimizing both distance sum and radius