Alignment of trees -- an alternative to tree edit

DOI10.1016/0304-3975(95)80015-8zbMath0873.68150OpenAlexW2147828873MaRDI QIDQ673642

Tao Jiang, Lusheng Wang, Zhang, Kaizhong

Publication date: 28 February 1997

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

Full work available at URL: https://doi.org/10.1016/0304-3975(95)80015-8

zbMATH Keywords

similarityalignment of trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Algebraic dynamic programming on trees ⋮ Supervised classification and mathematical optimization ⋮ A similarity measure for graphs with low computational complexity ⋮ Tai mapping hierarchy for rooted labeled trees through common subforest ⋮ Forest alignment with affine gaps and anchors, applied in RNA structure comparison ⋮ A survey on tree matching and XML retrieval ⋮ A metric for rooted trees with unlabeled vertices based on nested parentheses ⋮ A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes ⋮ A theory of subtree matching and tree kernels based on the edit distance concept ⋮ Algorithms for local similarity between forests ⋮ Comparing similar ordered trees in linear-time ⋮ Space efficient algorithms for ordered tree comparison ⋮ Computational methods in noncoding RNA research ⋮ Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems ⋮ Comparative Assessment of Alignment Algorithms for NGS Data: Features, Considerations, Implementations, and Future ⋮ Forest Alignment with Affine Gaps and Anchors ⋮ Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees ⋮ Finding similar consensus between trees: An algorithm and a distance hierarchy ⋮ Algorithms for finding a most similar subforest ⋮ Selected tree classifier combination based on both accuracy and error diversity ⋮ Identifying consensus of trees through alignment ⋮ Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm ⋮ A survey on tree edit distance and related problems ⋮ Data mining in an engineering design environment: OR applications from graph matching ⋮ Counting, Generating, Analyzing and Sampling Tree Alignments ⋮ Comparing trees via crossing minimization ⋮ An algebraic view of the relation between largest common subtrees and smallest common supertrees ⋮ On the complexity of comparing evolutionary trees ⋮ FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees ⋮ Alignment distance of regular tree languages ⋮ Alignment distance of regular tree languages ⋮ A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression. ⋮ Compositional properties of alignments ⋮ Decomposition algorithms for the tree edit distance problem ⋮ Graph comparison via nonlinear quantum search ⋮ Comparing and distinguishing the structure of biological branching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Optimization, approximation, and complexity classes
• On the editing distance between unordered labeled trees
• Some MAX SNP-hard results concerning unordered labeled trees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Threshold decomposition of gray-scale morphology into binary morphology
• A Tree-to-Tree Distance and Its Application to Cluster Analysis
• The Tree-to-Tree Correction Problem