Fixed-parameter algorithms for protein similarity search under mRNA structure constraints

DOI10.1016/j.jda.2008.03.004zbMath1154.05326OpenAlexW2060955779MaRDI QIDQ1002106

Guillaume Fertin, Guillaume Blin, Danny Hermelin, Stéphane Vialette

Publication date: 23 February 2009

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

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

zbMATH Keywords

fixed-parameter tractabilityparameterized complexitymRNA optimizationprotein similarityselenocysteine insertion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Genetics and epigenetics (92D10)

Related Items (4)

On Cutwidth Parameterized by Vertex Cover ⋮ On cutwidth parameterized by vertex cover ⋮ Unnamed Item ⋮ A Variable Neighbourhood Search approach to the Cutwidth Minimization Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Min Cut is NP-complete for edge weighted trees
• Graphs with small bandwidth and cutwidth
• The book thickness of a graph
• On triangulating planar graphs under the four-connectivity constraint
• Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots
• Tree-width, path-width, and cutwidth
• Crossing Number is NP-Complete
• Graph minors. II. Algorithmic aspects of tree-width
• Combinatorial Pattern Matching
• Crossing minimization in linear embeddings of graphs
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• SOFSEM 2004: Theory and Practice of Computer Science

This page was built for publication: Fixed-parameter algorithms for protein similarity search under mRNA structure constraints