License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2017.27
URN: urn:nbn:de:0030-drops-73364
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7336/
Bulteau, Laurent ;
Fertin, Guillaume ;
Komusiewicz, Christian
Beyond Adjacency Maximization: Scaffold Filling for New String Distances
Abstract
In Genomic Scaffold Filling, one aims at polishing in silico a draft genome, called scaffold. The scaffold is given in the form of an ordered set of gene sequences, called contigs. This is done by confronting the scaffold to an already complete reference genome from a close species. More precisely, given a scaffold S, a reference genome G and a score function f() between two genomes, the aim is to complete S by adding the missing genes from G so that the obtained complete genome S* optimizes f(S*, G). In this paper, we extend a model of Jiang et al. [CPM 2016] (i) by allowing the insertions of strings instead of single characters (i.e., some groups of genes may be forced to be inserted together) and (ii) by considering two alternative score functions: the first generalizes the notion of common adjacencies by maximizing the number of common k-mers between S* and G (k-Mer Scaffold Filling), the second aims at minimizing the number of breakpoints between S* and G (Min-Breakpoint Scaffold Filling). We study these problems from the parameterized complexity point of view, providing fixed-parameter (FPT) algorithms for both problems. In particular, we show that k-Mer Scaffold Filling is FPT wrt. parameter l, the number of additional k-mers realized by the completion of S—this answers an open question of Jiang et al. [CPM 2016]. We also show that Min-Breakpoint Scaffold Filling is FPT wrt. a parameter combining the number of missing genes, the number of gene repetitions and the target distance.
BibTeX - Entry
@InProceedings{bulteau_et_al:LIPIcs:2017:7336,
author = {Laurent Bulteau and Guillaume Fertin and Christian Komusiewicz},
title = {{Beyond Adjacency Maximization: Scaffold Filling for New String Distances}},
booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
pages = {27:1--27:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-039-2},
ISSN = {1868-8969},
year = {2017},
volume = {78},
editor = {Juha K{\"a}rkk{\"a}inen and Jakub Radoszewski and Wojciech Rytter},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7336},
URN = {urn:nbn:de:0030-drops-73364},
doi = {10.4230/LIPIcs.CPM.2017.27},
annote = {Keywords: computational biology, strings, FPT algorithms, kernelization}
}
|
Keywords: |
|
computational biology, strings, FPT algorithms, kernelization |
|
Collection: |
|
28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
30.06.2017 |
