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.014MaRDI QIDQ974736zbMATH OpenOpenAlexFDO

Authors Claire Herrbach, Alain Denise, Serge Dulucq

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

RNA structureaverage complexitytree alignmentRNA alignment

Mathematics Subject Classification ID

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

Recommendations

• The parameterized complexity of sequence alignment and consensus
• Aligning sequences via an evolutionary tree: complexity and approximation
• RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm.
• Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree
• Approximation algorithms for tree alignment with a given phylogeny
• A parallel algorithm for estimating the secondary structure in ribonucleic acids
• On the complexity of constrained sequences alignment problems

Cites work

• scientific article; zbMATH DE number 1305084 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• Alignment of trees -- an alternative to tree edit
• Analysis of tree edit distance algorithms
• Extending the Hardness of RNA Secondary Structure Comparison
• How to Compare Arc-Annotated Sequences: The Alignment Hierarchy
• Patterns in trees
• RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm.
• RNA secondary structures and their prediction
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems

Cited in

(2)

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

This page was built for publication: Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q974736)