Parameterized Complexity for Finding a Perfect Phylogeny from Mixed Tumor Samples
Wen-Horng Sheu, Biing-Feng Wang · SIAM Journal on Discrete Mathematics · 2023
Abstract. Motivated by an application in cancer genomics, Hajirasouliha and Raphael [ Proceedings of the 14 th International Workshop on Algorithms in Bioinformatics, 2014, pp. 354–367] proposed the split-row problem (SR). In this problem, an [Formula: see text] binary matrix [Formula: see text] is given. A split-row operation on [Formula: see text] is defined as replacing a row [Formula: see text] by [Formula: see text] rows [Formula: see text] whose bitwise OR is equal to [Formula: see text]. The cost of the operation is the number of additional rows induced, that is, [Formula: see text]. The goal is to find a sequence of split-row operations that transforms [Formula: see text] into a matrix corresponding to a perfect phylogeny and the total cost is minimized. Recently, Hujdurović et al. [ ACM Trans. Algorithms, 14 (2018), 26] proved the APX-hardness of SR and presented efficient exact and approximation algorithms. The parameterized study of SR was left as a direction for future work. Let [Formula: see text] denote the minimum total cost. This paper gives an [Formula: see text]-time exact algorithm for SR. This result indicates that SR is fixed-parameter tractable when parameterized by [Formula: see text]. In addition, in the worst case, our algorithm requires [Formula: see text] time, significantly improving the previous upper bound of [Formula: see text]. Hujdurović et al.’s exact algorithm can be modified to solve a variant of SR, called the distinct split-row problem (DSR). Our algorithm can be adapted to this variant as well. In addition, our algorithms can be extended to solve SR and DSR with the following additional constraint: only the rows in a given subset are allowed to be split.