Fixed-parameter algorithms for scaffold filling

DOI10.1016/j.tcs.2014.12.005zbMath1312.68237OpenAlexW2030886449MaRDI QIDQ2513609

Laurent Bulteau, Riccardo Dondi, Anna Paola Carrieri

Publication date: 28 January 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10446/35151

zbMATH Keywords

computational biologyfixed-parameter algorithmsgenome comparisonscaffold filling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Genetics and epigenetics (92D10) Algorithms on strings (68W32)

Related Items (6)

Parameterized tractability of the maximum-duo preservation string mapping problem ⋮ A Polynomial Time Solution for Permutation Scaffold Filling ⋮ A new approximation algorithm for contig-based genomic scaffold filling ⋮ Genomic Scaffold Filling: A Progress Report ⋮ On the solution bound of two-sided scaffold filling ⋮ Comparing incomplete sequences via longest common subsequence

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding approximate and constrained motifs in graphs
• On the approximability of the exemplar adjacency number problem for genomes with gene repetitions
• Variants of constrained longest common subsequence
• On the parameterized complexity of the repetition free longest common subsequence problem
• Complexity issues in vertex-colored graph pattern matching
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Finding and counting vertex-colored subtrees
• Probably optimal graph motifs
• Color-coding
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Fixed-parameter algorithms for scaffold filling