Computing the similarity of two sequences with nested arc annotations

DOI10.1016/J.TCS.2003.10.026MaRDI QIDQ1884953zbMATH OpenOpenAlexFDO

Authors Jens Gramm, Jiong Guo, Jochen Alber, Rolf Niedermeier

Publication date 27 October 2004

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

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

zbMATH Keywords

NP-completenessRNA secondary structureFixed-parameter tractabilityLongest common subsequenceArc-annotated sequencesSearch tree

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 2087047
• The longest common subsequence problem for sequences with nested arc annotations.
• scientific article; zbMATH DE number 1754611
• Arc-preserving subsequences of arc-annotated sequences
• scientific article; zbMATH DE number 1615278

Cites work

• scientific article; zbMATH DE number 1615278 (Why is no real title available?)
• scientific article; zbMATH DE number 2185647 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1954383 (Why is no real title available?)
• scientific article; zbMATH DE number 2080999 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• Algorithms on Strings, Trees and Sequences
• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
• Computing similarity between RNA structures
• Faster exact algorithms for hard problems: A parameterized point of view
• Longest common subsequences
• Near optimal multiple alignment within a band in polynomial time
• New methods for 3-SAT decision and worst-case analysis
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Parameterized complexity of finding subgraphs with hereditary properties.
• The longest common subsequence problem for sequences with nested arc annotations.
• The parameterized complexity of sequence alignment and consensus

Cited in

(10)

• A faster and more space-efficient algorithm for inferring arc-annotations of RNA sequences through alignment
• A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes
• scientific article; zbMATH DE number 2087047 (Why is no real title available?)
• Improved algorithms for largest cardinality 2-interval pattern problem
• Comparing RNA structures with biologically relevant operations cannot be done without strong combinatorial restrictions
• Fast arc-annotated subsequence matching in linear space
• scientific article; zbMATH DE number 2185647 (Why is no real title available?)
• Parameterized complexity of the arc-preserving subsequence problem
• A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs
• RNA multiple structural alignment with longest common subsequences

This page was built for publication: Computing the similarity of two sequences with nested arc annotations

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