Sorting by Weighted Reversals and Transpositions

Journal of computational biology: A journal of computational molecular cell biology

KlairtonLima Brito^2,1¹  AndreRodrigues Oliveira^1²  ZanoniDias^1³ 

[1] Address correspondence to: Klairton Lima Brito, Institute of Computing, University of Campinas, Avenida Albert Einstein, 1251, Campinas 13083-852, Brazil^2;Institute of Computing, University of Campinas, Campinas, Brazil^1;School of Technology, University of Campinas, Limeira, Brazil^3

关键词: approximation algorithms;    genome rearrangement;    reversals;    transpositions;    weighted operations;   

DOI  :  10.1089/cmb.2018.0257

学科分类：生物科学（综合）

来源: Mary Ann Liebert, Inc. Publishers

【 摘 要 】

Genome rearrangements are global mutations that change large stretches of DNA sequence throughout genomes. They are rare but accumulate during the evolutionary process leading to organisms with similar genetic material in different places and orientations within the genome. Sorting by Genome Rearrangements problems seek for minimum-length sequences of rearrangements that transform one genome into the other. These problems accept alternative versions that assign weights for each event, and the goal is to find a minimum-weight sequence. We study the Sorting by Weighted Reversals and Transpositions problem on signed permutations. In this study, we use weight 2 for reversals and 3 for transpositions and consider theoretical and practical aspects in our analysis. We present two algorithms with approximation factors of 5/3 and 3/2. We also developed a generic approximation algorithm to deal with different weights for reversals and transpositions, and we show the approximation factor reached in each scenario.

【 授权许可】

Unknown