标题:Scaffold Filling under the Breakpoint Distance
作者:Jiang, Haitao; Zheng, Chunfang; Sankoff, David; Zhu, Binhai
通讯作者:Jiang, H
作者机构:[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
来源:COMPARATIVE GENOMICS
出版年:2010
卷:6398
页码:83-92
DOI:10.1007/978-3-642-16181-0_8
摘要: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.
收录类别:CPCI-S;EI;SCOPUS
WOS核心被引频次:9
Scopus被引频次:12
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-78649967782&doi=10.1007%2f978-3-642-16181-0_8&partnerID=40&md5=922dc13fafe7b3c72e6f7904f64a7ef5
TOP