×

Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition. (English) Zbl 1436.68149

Summary: 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.

MSC:

68Q27 Parameterized complexity, tractability and kernelization
05A17 Combinatorial aspects of partitions of integers
05C05 Trees
68W40 Analysis of algorithms
92-08 Computational methods for problems pertaining to biology

Software:

MSOAR
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley · Zbl 0326.68005
[2] Amir, A.; Keselman, D., Maximum agreement subtree in a set of evolutionary trees: metrics and efficient algorithms, SIAM J. Comput., 26, 6, 1656-1669 (1997) · Zbl 0885.68071
[3] Bulteau, L.; Komusiewicz, C., Minimum common string partition parameterized by partition size is fixed-parameter tractable, (Chekuri, Chandra, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2014), SIAM), 102-121 · Zbl 1421.68253
[4] Chen, X.; Liu, L.; Liu, Z.; Jiang, T., On the minimum common integer partition problem, ACM Trans. Algorithms, 5, 1, 12 (2018) · Zbl 1445.90090
[5] Chen, X.; Zheng, J.; Fu, Z.; Nan, P.; Zong, Y.; Lonardi, S.; Jiang, T., Assignment of orthologous genes via genome rearrangement, IEEE/ACM Trans. Comput. Biol. Bioinform., 2, 4, 302-315 (2005)
[6] Damaschke, P., Minimum common string partition parameterized, (Crandall, Keith A.; Lagergren, Jens, International Workshop on Algorithms in Bioinformatics. International Workshop on Algorithms in Bioinformatics, WABI. International Workshop on Algorithms in Bioinformatics. International Workshop on Algorithms in Bioinformatics, WABI, Lecture Notes in Computer Science, vol. 5251 (2008), Springer), 87-98
[7] DasGupta, B.; He, X.; Jiang, T.; Li, M.; Tromp, J.; Wang, L.; Zhang, L., Computing distances between evolutionary trees, (Pardalos, Panos M.; Du, Ding-Zhu; Graham, Ronald L., Handbook of Combinatorial Optimization (2013), Springer: Springer New York), 747-781
[8] Downey, R. G.; Fellows, M. R., Fundamentals of Parameterized Complexity, Undergraduate Texts in Computer Science (2013), Springer: Springer London · Zbl 1358.68006
[9] Finden, C. R.; Gordon, A. D., Obtaining common pruned trees, J. Classif., 2, 1, 255-276 (1985)
[10] Fu, Z.; Chen, X.; Vacic, V.; Nan, P.; Zhong, Y.; Jiang, T., MSOAR: a high-throughput ortholog assignment system based on genome rearrangement, J. Comput. Biol., 14, 9, 1160-1175 (2007)
[11] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[12] Jiang, H.; Zhu, B.; Zhu, D.; Zhu, H., Minimum common string partition revisited, J. Comb. Optim., 23, 4, 519-527 (2012) · Zbl 1244.90195
[13] Kirkpatrick, B.; Reshef, Y.; Finucane, H.; Jiang, H.; Zhu, B.; Karp, R. M., Comparing pedigree graphs, J. Comput. Biol., 19, 9, 998-1014 (2012)
[14] Li, W.; Liu, H.; Wang, J.; Xiang, L.; Yang, Y., An improved linear kernel for complementary maximal strip recovery: simpler and smaller, Theor. Comput. Sci., 786, 55-66 (2019) · Zbl 1429.68340
[15] Shi, F.; Chen, J.; Feng, Q.; Wang, J., Approximating maximum agreement forest on multiple binary trees, Algorithmica, 76, 4, 867-889 (2016) · Zbl 1352.68288
[16] Shi, F.; Chen, J.; Feng, Q.; Wang, J., A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees, J. Comput. Syst. Sci., 97, 28-44 (2018) · Zbl 1400.92379
[17] Tai, K., The tree-to-tree correction problem, J. ACM, 26, 3, 422-433 (1979) · Zbl 0409.68040
[18] Tong, W.; Lin, G., An improved approximation algorithm for the minimum common integer partition problem, (Ahn, Hee-Kap; Shin, Chan-Su, Proceeding of the 25th International Symposium on Algorithms and Computation. Proceeding of the 25th International Symposium on Algorithms and Computation, ISAAC. Proceeding of the 25th International Symposium on Algorithms and Computation. Proceeding of the 25th International Symposium on Algorithms and Computation, ISAAC, Lecture Notes in Computer Science, vol. 8889 (2014), Springer), 353-364 · Zbl 1432.68585
[19] Woodruff, D. P., Better approximations for the minimum common integer partition problem, (Díaz, Josep; Jansen, Klaus; Rolim, José D. P.; Zwick, Uri, Proceeding of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. Proceeding of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX. Proceeding of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. Proceeding of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, Lecture Notes in Computer Science, vol. 4110 (2006), Springer), 248-259 · Zbl 1155.68586
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.