Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm

DOI10.1016/j.tcs.2010.01.014zbMath1208.68241OpenAlexW2151656734MaRDI QIDQ974736

Claire Herrbach, Alain Denise, Dulucq, Serge

Publication date: 7 June 2010

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

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

zbMATH Keywords

average complexityRNA structuretree alignmentRNA alignment

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Protein sequences, DNA sequences (92D20)

Related Items

Counting, Generating, Analyzing and Sampling Tree Alignments ⋮ Counting, Generating and Sampling Tree Alignments

Cites Work

• Unnamed Item
• Unnamed Item
• Alignment of trees -- an alternative to tree edit
• RNA secondary structures and their prediction
• RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm.
• Patterns in trees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• How to Compare Arc-Annotated Sequences: The Alignment Hierarchy
• Analysis of Tree Edit Distance Algorithms
• Extending the Hardness of RNA Secondary Structure Comparison