期刊
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS
卷 18, 期 6, 页码 2080-2093出版社
IEEE COMPUTER SOC
DOI: 10.1109/TCBB.2021.3077418
关键词
Genomics; Sorting; Approximation algorithms; Transforms; Bioinformatics; DNA; Phylogeny; Genome rearrangements; intergenic regions; reversals; transpositions
类别
资金
- National Counsel of Technological and Scientific Development, CNPq [400487/2016-0, 425340/2016-3, 140466/2018-5]
- Brazilian Federal Agency for the Support and Evaluation of Graduate Education, CAPES [831/15]
- Sao Paulo Research Foundation, FAPESP [2013/08293-7, 2015/11937-9, 2017/12646-3, 2019/27331-3]
- Fundacao de Amparo a Pesquisa do Estado de Sao Paulo (FAPESP) [19/27331-3] Funding Source: FAPESP
Genome rearrangements are events that affect large stretches of genomes during evolution. Considering intergenic regions can enhance distance estimation. Approximation algorithms have been developed for transposition distance and signed reversal and transposition distance.
Genome Rearrangements are events that affect large stretches of genomes during evolution. Many mathematical models have been used to estimate the evolutionary distance between two genomes based on genome rearrangements. However, most of them focused on the (order of the) genes of a genome, disregarding other important elements in it. Recently, researchers have shown that considering regions between each pair of genes, called intergenic regions, can enhance distance estimation in realistic data. Two of the most studied genome rearrangements are the reversal, which inverts a sequence of genes, and the transposition, which occurs when two adjacent gene sequences swap their positions inside the genome. In this work, we study the transposition distance between two genomes, but we also consider intergenic regions, a problem we name Sorting by Intergenic Transpositions. We show that this problem is NP-hard and propose two approximation algorithms, with factors 3.5 and 2.5, considering two distinct definitions for the problem. We also investigate the signed reversal and transposition distance between two genomes considering their intergenic regions. This second problem is called Sorting by Signed Intergenic Reversals and Intergenic Transpositions. We show that this problem is NP-hard and develop two approximation algorithms, with factors 3 and 2.5. We check how these algorithms behave when assigning weights for genome rearrangements. Finally, we implemented all these algorithms and tested them on real and simulated data.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据