Beyond Adjacency Maximization: Scaffold Filling for New String Distances
Beyond Adjacency Maximization: Scaffold Filling for New String Distances
复制标题
DOI：
10.4230/lipics.cpm.2017.27
复制
发表时间：
2017
期刊：
影响因子：
5.4
通讯作者：
L. Bulteau;G. Fertin;Christian Komusiewicz
中科院分区：
文献类型：
--
作者：
L. Bulteau;G. Fertin;Christian Komusiewicz
在基因组支架填充中，人们的目标是在计算机上抛光基因组草图，称为支架。支架以一组有序的基因序列的形式给出，称为重叠群。这是通过使支架面对来自近缘物种的已经完整的参考基因组来完成的。更确切地说，给定支架S、参考基因组G和两个基因组之间的评分函数f（），目标是通过添加G中缺失的基因来完成S，使得获得的完整基因组S * 优化f（S *，G）。在本文中，我们扩展了Jiang等人的模型。[CPM 2016]（i）通过允许插入字符串而不是单个字符（即，一些基因组可能被迫插入在一起）和（ii）通过考虑两个可选择的评分函数：第一个通过最大化S * 和G之间的共同k-mer的数量（k-Mer骨架填充）来概括共同邻接的概念，第二个旨在最小化S * 和G之间的断点的数量（最小断点骨架填充）。我们研究这些问题的参数化的复杂性的角度来看，提供固定参数（FPT）算法的问题。特别是，我们表明，k-Mer支架填充是FPT wrt。参数，通过完成S-实现的额外k-聚体的数量，这回答了Jiang等人的一个未决问题[CPM 2016]。我们还表明，最小断点支架填充是FPT wrt。组合缺失基因的数量、基因重复的数量和目标距离的参数。
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 , 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.