An improved approximation algorithm for the reversal and transposition distance considering gene order and intergenic sizes

Author(s)

Brito, Klairton L. ^[1] ; Oliveira, Andre R. ^[1] ; Alexandrino, Alexsandro O. ^[1] ; Dias, Ulisses ^[2] ; Dias, Zanoni ^[1]

Affiliation

^[1] Univ Estadual Campinas, Inst Comp, 1251 Albert Einstein Ave, BR-13083852 Campinas - Brazil

^[2] Univ Estadual Campinas, Sch Technol, 1888 Paschoal Marmo St, BR-13484332 Limeira - Brazil

• Document type: Journal article
• Source: Algorithms for Molecular Biology; v. 16, n. 1 DEC 29 2021.
• Web of Science Citations: 0

Abstract

Background In the comparative genomics field, one of the goals is to estimate a sequence of genetic changes capable of transforming a genome into another. Genome rearrangement events are mutations that can alter the genetic content or the arrangement of elements from the genome. Reversal and transposition are two of the most studied genome rearrangement events. A reversal inverts a segment of a genome while a transposition swaps two consecutive segments. Initial studies in the area considered only the order of the genes. Recent works have incorporated other genetic information in the model. In particular, the information regarding the size of intergenic regions, which are structures between each pair of genes and in the extremities of a linear genome. Results and conclusions In this work, we investigate the sorting by intergenic reversals and transpositions problem on genomes sharing the same set of genes, considering the cases where the orientation of genes is known and unknown. Besides, we explored a variant of the problem, which generalizes the transposition event. As a result, we present an approximation algorithm that guarantees an approximation factor of 4 for both cases considering the reversal and transposition (classic definition) events, an improvement from the 4.5-approximation previously known for the scenario where the orientation of the genes is unknown. We also present a 3-approximation algorithm by incorporating the generalized transposition event, and we propose a greedy strategy to improve the performance of the algorithms. We performed practical tests adopting simulated data which indicated that the algorithms, in both cases, tend to perform better when compared with the best-known algorithms for the problem. Lastly, we conducted experiments using real genomes to demonstrate the applicability of the algorithms. (AU)

• FAPESP's process: 19/27331-3 - Sorting by genome rearrangements problems
• Grantee: André Rodrigues Oliveira
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
• Grantee: Flávio Keidi Miyazawa
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 17/12646-3 - Déjà vu: feature-space-time coherence from heterogeneous data for media integrity analytics and interpretation of events
• Grantee: Anderson de Rezende Rocha
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 13/08293-7 - CCES - Center for Computational Engineering and Sciences
• Grantee: Munir Salomao Skaf
• Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC