基因複製樹問題的NP-hardness性質

The NP-hardness property of the copy-number tree problem

楊宗頤(Tsung-Yi Yang) ； 楊敦翔(Dun-Siang Yang) ； 謝維華(Wei-Hua Hsieh)

《東海科學》 21卷 (2019/07) Pp. 1-14

https://doi.org/10.29723/TS.201907_21.0001

摘要

癌是個動態過程，快速的突變形成複雜的腫瘤基因組，了解其與正常基因組的差異及其演化過程，可幫助我們預測疾病的進展與可能的醫療介入。為探討癌細胞的基因演化過程，El-Kebir et al.建立基因複製樹問題，並證明其為NP-hard，但我們發現該證明並不正確。我們建立修訂基因複製樹問題，並建立了一個多項式轉換，將修訂最簡約演化樹問題轉換至修訂基因複製樹問題。

關鍵字

癌 ； 基因組重新排列 ； 基因複製向量 ； 演化樹 ； 最簡約假設 ； NP-hard

並列摘要

Cancer is a dynamic process. Rapid mutations form complex tumor genomes. Understanding their differences with normal genomes and their evolution can help predict the evolution of the disease and possible medical interventions. To predict the evolution of cancer cells, El-Kebir et al. established the copy-number tree problem and proved it to be NP-hard. We found that the proof is not exactly correct. Thus, we established the revised copy-number tree problem and transformed the revised maximum parsimony phylogeny problem to the revised copy-number tree problem by a polynomial transformation.

並列關鍵字

Cancer ； Genome rearrangement ； Copy number profile ； Phylogeny ； Maximum parsimony ； NP-hard