Alignment of trees -- an alternative to tree edit
From MaRDI portal
Publication:673642
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
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
