Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition

Computational biology is mainly concerned with discovering an object from a given set of observations that are supposed to be good approximations of the real object. Two important steps here are to define a way to measure the distance between different objects and to calculate the distance between two given objects. The main problem is then to find an object that has the minimum total distance to the given observations. We study two NP-hard problems formulated in computational biology. The minimum tree cut/paste distance problem asks for the minimum number of cut/paste operations we need to transform a tree to another tree. The minimum common integer partition problem asks for a minimum-cardinality integer partition of a number that refines two given integer partitions of the same number. We give parameterized algorithms for both problems.

Authors

• Jie You
• Feng Shi
• Jianxin Wang
• Qilong Feng

Keywords

• Fixed-parameter tractability
• Minimum common integer partition
• Minimum common string partition