A Polynomial-Time Algorithm for Computing the Translocation Syntenic Distance of Special Graphs

The Minimum Synteny problem is a well-known NP-hard problem that aims to identify the minimum syntenic distance between two genomes. In this paper, we focus on solving a variant of the problem, called the Minimum Translocation Synteny problem, where we consider the minimum number of translocations to transform one genome to another. We propose a polynomial-time algorithm that computes for the translocation syntenic distances between two genomes with square instances. The MinTranSyn algorithm presents a solution to the translocation syntenic distance problem by using a prioritization method in selecting an index to be isolated and vertices to be translocated. The MinTranSyn algorithm is devised for genomes with square instances having square-connected components. With this, the algorithm presented by Belenzo8 was improved with respect to the number of translocations. We showed the quality of the algorithm is bounded above by the total number of chromosomes in a genome for synteny graphs that are 2-regular, wheel, and acyclic.