A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes

DOI10.1016/j.tcs.2010.11.020zbMath1206.68378OpenAlexW2053905301WikidataQ60704253 ScholiaQ60704253MaRDI QIDQ627175

Aïda Ouangraoua, Valentin Guignon, Sylvie Hamel, Cedric Chauve

Publication date: 21 February 2011

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

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

zbMATH Keywords

dynamic programmingsequence alignmentarc-annotated sequences

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Algorithms on strings (68W32)

Uses Software

• Rfam
• MARNA

Cites Work

• Alignment of trees -- an alternative to tree edit
• The longest common subsequence problem for arc-annotated sequences
• Local similarity between quotiented ordered trees
• String processing and information retrieval. 12th international conference, SPIRE 2005, Buenos Aires, Argentina, November 2--4, 2005. Proceedings
• RNA pseudoknot structures with arc-length \(\geq 3\) and stack-length \(\geq \sigma \)
• Computing similarity between RNA structures
• The longest common subsequence problem for sequences with nested arc annotations.
• Fast detection of common sequence structure patterns in RNAs
• Decomposition algorithms for the tree edit distance problem
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• How to Compare Arc-Annotated Sequences: The Alignment Hierarchy
• Extending the Hardness of RNA Secondary Structure Comparison
• Algorithms on Strings, Trees and Sequences
• An Optimal Decomposition Algorithm for Tree Edit Distance