Approximation of RNA multiple structural alignment

DOI10.1016/j.jda.2010.03.002zbMath1230.68224OpenAlexW2045486252MaRDI QIDQ655441

Stéphane Vialette, Marcin Kubica, Romeo Rizzi, Tomasz Walen

Publication date: 4 January 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2010.03.002

zbMATH Keywords

largest nested linear subgraph problemlinear graphsRNA structural alignment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Protein sequences, DNA sequences (92D20) Graph algorithms (graph-theoretic aspects) (05C85) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Trapezoid graphs and generalizations, geometry and algorithms
• A computational model for RNA multiple structural alignment
• Trapezoid graphs and their coloring
• The longest common subsequence problem for sequences with nested arc annotations.
• On the computational complexity of 2-interval pattern matching problems
• On powers of \(m\)-trapezoid graphs
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Multiple Genome Alignment: Chaining Algorithms Revisited
• Algorithms for Loop Matchings
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Computing and Combinatorics