Incorporating intergenic regions into reversal and transposition distances with indels

Author(s)

Alexandrino, Alexsandro Oliveira ^[1] ; Oliveira, Andre Rodrigues ^[1] ; Dias, Ulisses ^[2] ; Dias, Zanoni ^[1]

Affiliation

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

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

• Document type: Journal article
• Source: JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY; v. 19, n. 6, SI DEC 2021.
• Web of Science Citations: 0

Abstract

Problems in the genome rearrangement field are often formulated in terms of pairwise genome comparison: given two genomes G(1) and G(2), find the minimum number of genome rearrangements that may have occurred during the evolutionary process. This broad definition lacks at least two important considerations: the first being which features are extracted from genomes to create a useful mathematical model, and the second being which types of genome rearrangement events should be represented. Regarding the first consideration, seminal works in the genome rearrangement field solely used gene order to represent genomes as permutations of integer numbers, neglecting many important aspects like gene duplication, intergenic regions, and complex interactions between genes. Regarding the second consideration, some rearrangement events are widely studied such as reversals and transpositions. In this paper, we shed light on the first consideration and created a model that takes into account gene order and the number of nucleotides in intergenic regions. In addition, we consider events of reversals, transpositions, and indels (insertions and deletions) of genomic material. We present a 4-approximation algorithm for reversals and indels, a 4:5-approximation algorithm for transpositions and indels, and a 6-approximation for reversals, transpositions, and indels. (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: 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
• 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