Abstract
Many tools from Computational Biology compute distances between genomes by counting the number of genome rearrangement events, such as reversals of a segment of genes. Most approaches to model these problems consider some simplifications such as ignoring nucleotides outside genes (the so-called intergenic regions), or assuming that just a single copy of each gene exists in the genomes. Recent works made advancements in more general models considering replicated genes and the number of nucleotides in intergenic regions. Our work aims at adapting those results by applying some flexibilization to match intergenic regions that do not have the same number of nucleotides. We propose the Signed Flexible Intergenic Reversal Distance problem, which seeks the minimum number of reversals necessary to transform one genome into the other and encodes the genomes using flexible intergenic region information while also allowing multiple copies of a gene. We show the relationship of this problem with the Signed Minimum Common Flexible Intergenic String Partition problem and use a 2k-approximation to the partition problem to show a 8k-approximation to the distance problem, where k is the maximum number of copies of a gene in the genomes.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bafna, V., Pevzner, P.A.: Sorting by transpositions. SIAM J. Disc. Math. 11(2), 224–240 (1998)
Biller, P., Guéguen, L., Knibbe, C., Tannier, E.: Breaking good: accounting for fragility of genomic regions in rearrangement distance estimation. Genome Biol. Evol. 8(5), 1427–1439 (2016)
Biller, P., Knibbe, C., Beslon, G., Tannier, E.: Comparative genomics on artificial life. In: Beckmann, A., Bienvenu, L., Jonoska, N. (eds.) CiE 2016. LNCS, vol. 9709, pp. 35–44. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-40189-8_4
Brito, K.L., Alexandrino, A.O., Oliveira, A.R., Dias, U., Dias, Z.: Genome rearrangement distance with a flexible intergenic regions aspect. IEEE/ACM Trans. Comput. Biol. Bioinf. 20(3), 1641–1653 (2023)
Brito, K.L., Oliveira, A.R., Alexandrino, A.O., Dias, U., Dias, Z.: Reversal and transposition distance of genomes considering flexible intergenic regions. Procedia Comput. Sci. 195, 21–29 (2021)
Fertin, G., Jean, G., Tannier, E.: Algorithms for computing the double cut and join distance on both gene order and intergenic sizes. Algor. Molec. Biol. 12(1), 16 (2017)
Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J. ACM 46(1), 1–27 (1999)
Kolman, P., Waleń, T.: Reversal distance for strings with duplicates: linear time approximation using hitting set. In: Erlebach, T., Kaklamanis, C. (eds.) WAOA 2006. LNCS, vol. 4368, pp. 279–289. Springer, Heidelberg (2007). https://doi.org/10.1007/11970125_22
Oliveira, A.R., et al.: Sorting signed permutations by intergenic reversals. IEEE/ACM Trans. Comput. Biol. Bioinf. 18(6), 2870–2876 (2021)
Radcliffe, A.J., Scott, A.D., Wilmer, E.L.: Reversals and transpositions over finite alphabets. SIAM J. Disc. Math. 19(1), 224–244 (2005)
Siqueira, G., Alexandrino, A.O., Dias, Z.: Signed rearrangement distances considering repeated genes and intergenic regions. In: Proceedings of 14th International Conference on Bioinformatics and Computational Biology (BICoB 2022), vol. 83, pp. 31–42 (2022)
Acknowledgment
This work was supported by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001 and the São Paulo Research Foundation, FAPESP (grants 2013/08293-7 , 2021/13824-8 , and 2022/13555-0 ).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Siqueira, G., Oliveira Alexandrino, A., Rodrigues Oliveira, A., Jean, G., Fertin, G., Dias, Z. (2023). Approximating Rearrangement Distances with Replicas and Flexible Intergenic Regions. In: Guo, X., Mangul, S., Patterson, M., Zelikovsky, A. (eds) Bioinformatics Research and Applications. ISBRA 2023. Lecture Notes in Computer Science(), vol 14248. Springer, Singapore. https://doi.org/10.1007/978-981-99-7074-2_19
Download citation
DOI: https://doi.org/10.1007/978-981-99-7074-2_19
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-99-7073-5
Online ISBN: 978-981-99-7074-2
eBook Packages: Computer ScienceComputer Science (R0)