An algorithm and applications to sequence alignment with weighted constraints

DOI10.1142/S012905411000712XMaRDI QIDQ5187851zbMATH OpenFDO

Authors Yung-Hsing Peng, Chang-Biau Yang, Kuo-Tsung Tseng, Kuo-Si Huang

Publication date 9 March 2010

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S012905411000712X

zbMATH Keywords

algorithmlongest common subsequencesequence alignmentweighted constraint

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computing methodologies for text processing; mathematical typography (68U15)

Recommendations

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

Cites work

• A fast algorithm for computing longest common subsequences
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• A linear space algorithm for computing maximal common subsequences
• A simple algorithm for the constrained sequence problems
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Dynamic programming algorithms for the mosaic longest common subsequence problem
• Efficient algorithms for finding interleaving relationship between sequences
• Efficient algorithms for regular expression constrained sequence alignment
• New efficient algorithms for the LCS and constrained LCS problems
• The constrained longest common subsequence problem

Cited in

(22)

• Non-approximability of weighted multiple sequence alignment for arbitrary metrics
• Sequence comparison with concave weighting functions
• Constrained sequence alignment
• A polyhedral approach to sequence alignment problems
• A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint
• Weighted sequence graphs: Boosting iterated dynamic programming using locally suboptimal solutions
• Finding the gapped longest common subsequence by incremental suffix maximum queries
• A dynamic programming solution to a generalized LCS problem
• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
• Constrained sequence alignment: A general model and the hardness results
• Constrained pairwise and center-star sequences alignment problems
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• scientific article; zbMATH DE number 1796955 (Why is no real title available?)
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• A parallel algorithm for the constrained multiple sequence alignment problem designed for GPUs
• Sequence alignment with arbitrary steps and further generalizations, with applications to alignments in linguistics
• Implementation and Application of Automata
• Computational and Information Science
• Parametric sequence alignment with constraints
• Linear-space S-table algorithms for the longest common subsequence problem
• The generalized constrained longest common subsequence in the run-length encoded format

This page was built for publication: An algorithm and applications to sequence alignment with weighted constraints

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