New algorithms for structure informed genome rearrangement
Authors: Ozeri Eden , Zehavi Meirav , Ziv-Ukelson Michal 
Published: December 2023

AbstractWe define two new computational problems in the domain of perfect genome rearrangements, and propose three algorithms to solve them. The rearrangement scenarios modeled by the problems consider Reversal and Block Interchange operations, and a PQ-tree is utilized to guide the allowed operations and to compute their weights. In the first problem,$$\mathsf {Constrained \ TreeToString \ Divergence}$$ConstrainedTreeToStringDivergence($$\textsf{CTTSD}{}$$CTTSD), we define the basic structure-informed rearrangement measure. Here, we assume that the gene order members of the gene cluster from which the PQ-tree is constructed are permutations. The PQ-tree representing the gene cluster is ordered such that the series of gene IDs spelled by its leaves is equivalent to that of the reference gene order. Then, a structure-informed genome rearrangement distance is computed between the ordered PQ-tree and the target gene order. The second problem,$$\mathsf {TreeToString \ Divergence}$$TreeToStringDivergence($$\textsf{TTSD}{}$$TTSD), generalizes$$\textsf{CTTSD}{}$$CTTSD, where the gene order members are not necessarily permutations and the structure informed rearrangement measure is extended to also consider up to$$d_S$$dSand$$d_T$$dTgene insertion and deletion operations, respectively, when modelling the PQ-tree informed divergence process from the reference gene order to the target gene order. The first algorithm solves$$\textsf{CTTSD}{}$$CTTSDin$$O(n \gamma ^2 \cdot (m_p \cdot 1.381^\gamma + m_q))$$O(nγ2·(mp·1.381γ+mq))time and$$O(n^2)$$O(n2)space, where$$\gamma $$γis the maximum number of children of a node,nis the length of the string and the number of leaves in the tree, and$$m_p$$mpand$$m_q$$mqare the number of P-nodes and Q-nodes in the tree, respectively. If one of the penalties of$$\textsf{CTTSD}$$CTTSDis 0, then the algorithm runs in$$O(n m \gamma ^2)$$O(nmγ2)time and$$O(n^2)$$O(n2)space. The second algorithm solves$$\textsf{TTSD}{}$$TTSDin$$O(n^2 \gamma ^2 {d_T}^2 {d_S}^2\,m^2 (m_p \cdot 5^\gamma \gamma + m_q))$$O(n2γ2dT2dS2m2(mp·5γγ+mq))time and$$O(d_T d_S m (m n + 5^\gamma ))$$O(dTdSm(mn+5γ))space, where$$\gamma $$γis the maximum number of children of a node,nis the length of the string,mis the number of leaves in the tree,$$m_p$$mpand$$m_q$$mqare the number of P-nodes and Q-nodes in the tree, respectively, and allowing up to$$d_T$$dTdeletions from the tree and up to$$d_S$$dSdeletions from the string. The third algorithm is intended to reduce the space complexity of the second algorithm. It solves a variant of the problem (where one of the penalties of$$\textsf{TTSD}$$TTSDis 0) in$$O(n \gamma ^2 {d_T}^2 {d_S}^2\,m^2 (m_p \cdot 4^{\gamma }\gamma ^2n(d_T+d_S+m+n) + m_q))$$O(nγ2dT2dS2m2(mp·4γγ2n(dT+dS+m+n)+mq))time and$$O(\gamma ^2 n m^2 d_T d_S (d_T+d_S+m+n))$$O(γ2nm2dTdS(dT+dS+m+n))space. The algorithm is implemented as a software tool, denoted MEM-Rearrange, and applied to the comparative and evolutionary analysis of 59 chromosomal gene clusters extracted from a dataset of 1487 prokaryotic genomes.