Extending the Hardness of RNA Secondary Structure Comparison

DOI10.1007/978-3-540-74450-4_13zbMath1176.92018OpenAlexW1546427870WikidataQ29028118 ScholiaQ29028118MaRDI QIDQ3611904

Guillaume Fertin, Irena Rusu, Christine Sinoquet, Guillaume Blin

Publication date: 3 March 2009

Published in: Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74450-4_13

zbMATH Keywords

computational biologyNP-hardnessRNA structuresedit distancearc-annotated sequences

Mathematics Subject Classification ID

Biochemistry, molecular biology (92C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Systems biology, networks (92C42)

Related Items

A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes, Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm