Recovering rearranged cancer chromosomes from karyotype graphs
Recovering rearranged cancer chromosomes from karyotype graphs
复制标题
DOI：
10.1186/s12859-019-3208-4
复制
发表时间：
2019-12-17
影响因子：
3
通讯作者：
Schatz, Michael C.
中科院分区：
文献类型：
--
作者：
Aganezov, Sergey;Zban, Ilya;Schatz, Michael C.
背景：许多癌症基因组广泛重排，染色体核型高度异常。癌症基因组的结构和拷贝数变化可以通过序列读取到参考基因组的异常映射来确定。最近有可能将这两种类型的大规模变异调和成重排癌症基因组的核型图。然而，这种表述并不能直接描述潜在的重排癌症染色体的线性和/或圆形结构，从而限制了对癌症基因组的体细胞进化过程以及大规模基因组重排带来的功能基因组变化的可能分析。结果：在这里，我们通过引入一种从核型图中恢复重排癌症染色体的新方法框架来解决上述限制。对于癌症核型图，我们制定了一个欧拉分解问题（EDP），寻找由图确定的线性和/或圆形重排癌症染色体的集合。我们推导并证明了几种EDP变量的计算复杂度。然后，我们证明了癌症核型图的欧拉分解并不总是唯一的，并提出了从癌症核型图中恢复明确的癌症组群的一致Contig覆盖问题（CCCP），并描述了一种能够在多项式时间内解决CCCP的新算法CCR。我们将CCR应用于前列腺癌数据集，并证明即使潜在的癌症基因组高度重排，它也能够持续地恢复大型癌症基因组。结论：CCR可以从核型图中恢复重排的癌症基因组，从而解决了现有的推断重排癌症基因组染色体结构的局限性，并促进了我们对癌症患者/癌症特异性以及整体遗传不稳定性的理解。
Background: Many cancer genomes are extensively rearranged with highly aberrant chromosomal karyotypes. Structural and copy number variations in cancer genomes can be determined via abnormal mapping of sequenced reads to the reference genome. Recently it became possible to reconcile both of these types of large-scale variations into a karyotype graph representation of the rearranged cancer genomes. Such a representation, however, does not directly describe the linear and/or circular structure of the underlying rearranged cancer chromosomes, thus limiting possible analysis of cancer genomes somatic evolutionary process as well as functional genomic changes brought by the large-scale genome rearrangements.Results: Here we address the aforementioned limitation by introducing a novel methodological framework for recovering rearranged cancer chromosomes from karyotype graphs. For a cancer karyotype graph we formulate an Eulerian Decomposition Problem (EDP) of finding a collection of linear and/or circular rearranged cancer chromosomes that are determined by the graph. We derive and prove computational complexities for several variations of the EDP. We then demonstrate that Eulerian decomposition of the cancer karyotype graphs is not always unique and present the Consistent Contig Covering Problem (CCCP) of recovering unambiguous cancer contigs from the cancer karyotype graph, and describe a novel algorithm CCR capable of solving CCCP in polynomial time. We apply CCR on a prostate cancer dataset and demonstrate that it is capable of consistently recovering large cancer contigs even when underlying cancer genomes are highly rearranged.Conclusions: CCR can recover rearranged cancer contigs from karyotype graphs thereby addressing existing limitation in inferring chromosomal structures of rearranged cancer genomes and advancing our understanding of both patient/cancer-specific as well as the overall genetic instability in cancer.