On the complexity of constrained sequences alignment problems

DOI10.1007/978-3-319-08016-1_28MaRDI QIDQ3188858zbMATH OpenOpenAlexFDO

Authors Yong Zhang, Joseph Wun-Tat Chan, Deshi Ye, Feng Zhang, Francis Y. L. Chin, Hing-Fung Ting, Jianyu Shi

Publication date 2 September 2014

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-08016-1_28

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Recommendations

• Constrained pairwise and center-star sequences alignment problems
• Constrained sequence alignment: A general model and the hardness results
• Implementation and Application of Automata
• A fast algorithm for the constrained multiple sequence alignment problem
• A simple algorithm for the constrained sequence problems

Cited in

(16)

• Non-approximability of weighted multiple sequence alignment for arbitrary metrics
• An algorithm for computing the restriction s|caffold assignment problem in computational biology
• On computing all suboptimal alignments
• A polyhedral approach to sequence alignment problems
• A linear-space algorithm for the substring constrained alignment problem
• On the complexity of sequence to graph alignment
• Constrained sequence alignment: A general model and the hardness results
• scientific article; zbMATH DE number 2086217 (Why is no real title available?)
• Constrained pairwise and center-star sequences alignment problems
• Sequence comparison with mixed convex and concave costs
• scientific article; zbMATH DE number 1796955 (Why is no real title available?)
• Sequence alignment with arbitrary steps and further generalizations, with applications to alignments in linguistics
• Complexity of biological sequence alignment
• Parametric sequence alignment with constraints
• Consistency of optimal sequence alignments
• Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm

This page was built for publication: On the complexity of constrained sequences alignment problems

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