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

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

Laurent Tichit, Dulucq, Serge

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, Bilateral similarity function: a novel and universal method for similarity analysis of biological sequences, A simple method to analyze the similarity of biological sequences based on the fuzzy theory, Use of linear regression model to compare RNA secondary structures, An algebraic view of the relation between largest common subtrees and smallest common supertrees, Decomposition algorithms for the tree edit distance problem, Algebraic dynamic programming on trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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