Constrained sequence alignment: A general model and the hardness results

DOI10.1016/j.dam.2007.06.016zbMath1123.92008OpenAlexW2106782090MaRDI QIDQ2462385

Yun-Sheng Chung, Chin Lung Lu, Chuan Yi Tang

Publication date: 30 November 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.06.016

zbMATH Keywords

constrained sequence alignmentnonapproximabilityNPO-completeness

Mathematics Subject Classification ID

Biochemistry, molecular biology (92C40) Complexity and performance of numerical algorithms (65Y20)

Related Items (1)

Practical regular expression constrained sequence alignment

Uses Software

• PSIPRED
• MuSiC

Cites Work

• Unnamed Item
• Unnamed Item
• The NPO-completeness of the longest Hamiltonian cycle problem
• Efficient methods for multiple sequence alignment with guaranteed error bounds
• Approximation algorithms for multiple sequence alignment
• Proof verification and the hardness of approximation problems
• Efficient Algorithms for Regular Expression Constrained Sequence Alignment
• Combinatorial Pattern Matching
• The complexity of multiple sequence alignment with SP-score that is a metric

This page was built for publication: Constrained sequence alignment: A general model and the hardness results