摘要
Motivated by an application in cancer genomics, Hajirasouliha and Raphael [Proceedings of the 14th International Workshop on Algorithms in Bioinformatics, 2014, pp. 354-367] proposed the split-row problem (SR). In this problem, an m x n binary matrix M is given. A split-row operation on M is defined as replacing a row r by k > 1 rows r((1)), r((2)),..., r((k)) whose bitwise OR is equal to r. The cost of the operation is the number of additional rows induced, that is, k - 1. The goal is to find a sequence of split-row operations that transforms M into a matrix corresponding to a perfect phylogeny and the total cost is minimized. Recently, Hujdurovic 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 epsilon(M) denote the minimum total cost. This paper gives an O*(2(min(n,2 epsilon(M)))-time exact algorithm for SR. This result indicates that SR is fixed-parameter tractable when parameterized by epsilon(M). In addition, in the worst case, our algorithm requires O* (2(n)) time, significantly improving the previous upper bound of O* (n(n)). Hujdurovic 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.
