标题：Scaffold Filling under the Breakpoint Distance
作者：Jiang, Haitao; Zheng, Chunfang; Sankoff, David; Zhu, Binhai
作者机构：[Jiang, Haitao; Zhu, Binhai] Montana State Univ, Dept Comp Sci, Bozeman, MT 59717 USA.; [Jiang, Haitao] Shandong Univ, Sch Comp Sci & Technol, Jinan 更多
会议名称：International RECOMB Workshop on Comparative Genomics
会议日期：OCT 09-11, 2010
摘要：Motivated by the trend of genome sequencing without completing the sequence of the whole genomes, Munoz et al. recently studied the problem of filling an incomplete multichromosomal genome (or scaffold) I with respect to a complete target genome G such that the resulting genomic distance between I' and G is minimized, where I' is the corresponding filled scaffold. We call this problem the one-sided scaffold filling problem. In this paper, we follow Munoz et al. to investigate the scaffold filling problem under the breakpoint distance for the simplest unichromosomal genomes. When the input genome contains no gene repetition (i.e., is a fragment of a permutation), we show that the two-sided scaffold filling problem is polynomially solvable. However, when the input genome contains some genes which appear twice, even the one-sided scaffold filling problem becomes NP-complete. Finally, using the ideas for solving the two-sided scaffold filling problem under the breakpoint distance we show that the two-sided scaffold filling problem under the genomic/rearrangement distance is also polynomially solvable.