RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm.

DOI10.1016/S0304-3975(03)00323-2zbMath1060.68027MaRDI QIDQ1426469

Dulucq, Serge, Laurent Tichit

Publication date: 14 March 2004

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

zbMATH Keywords

RNA secondary structure; Generating function; Complexity analysis; Labeled ordered tree

Mathematics Subject Classification ID

68P10: Searching and sorting

Related Items

Local similarity between quotiented ordered trees, Comparing similar ordered trees in linear-time, Learning probabilistic models of tree edit distance, Variations on RNA folding and alignment: Lessons from Benasque, Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm, An algebraic view of the relation between largest common subtrees and smallest common supertrees, Decomposition algorithms for the tree edit distance problem

Cites Work

• Enumerations of ordered trees
• The tree-to-tree editing problem
• Linear trees and RNA secondary structure
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• The Tree-to-Tree Correction Problem
• Algorithms on Strings, Trees and Sequences
• The String-to-String Correction Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item