Sorting by reversals and block-interchanges with various weight assignments

BACKGROUND: A classical problem in studying genome rearrangements is understanding the series of rearrangement events involved in transforming one genome into another in accordance with the parsimonious principle when two genomes with the same set of genes differ in gene order. The most studied even...

Descripción completa

Detalles Bibliográficos
Autores principales: Lin, Ying Chih, Lin, Chun-Yuan, Lin, Chunhung Richard
Formato: Texto
Lenguaje:English
Publicado: BioMed Central 2009
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2800848/
https://www.ncbi.nlm.nih.gov/pubmed/19958558
http://dx.doi.org/10.1186/1471-2105-10-398
_version_ 1782175869857431552
author Lin, Ying Chih
Lin, Chun-Yuan
Lin, Chunhung Richard
author_facet Lin, Ying Chih
Lin, Chun-Yuan
Lin, Chunhung Richard
author_sort Lin, Ying Chih
collection PubMed
description BACKGROUND: A classical problem in studying genome rearrangements is understanding the series of rearrangement events involved in transforming one genome into another in accordance with the parsimonious principle when two genomes with the same set of genes differ in gene order. The most studied event is the reversal, but an increasing number of reports have considered reversals along with other genome rearrangement events. Some recent studies have investigated the use of reversals and block-interchanges simultaneously with a weight proportion of 1:2. However, there has been less progress towards exploring additional combinations of weights. RESULTS: In this paper, we present several approaches to examine genome rearrangement problems by considering reversals and block-interchanges together using various weight assignments. An exact algorithm for the weight proportion of 1:2 is developed, and then, its idea is extended to design approximation algorithms for other weight assignments. The results of our simulations suggest that the performance of our approximation algorithm is superior to its theoretical expectation. CONCLUSION: If the weight of reversals is no more than that of block-interchanges, our algorithm provides an acceptable solution for the transformation of two permutations. Nevertheless whether there are more tractable results for studying the two events remains open.
format Text
id pubmed-2800848
institution National Center for Biotechnology Information
language English
publishDate 2009
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-28008482010-01-01 Sorting by reversals and block-interchanges with various weight assignments Lin, Ying Chih Lin, Chun-Yuan Lin, Chunhung Richard BMC Bioinformatics Research article BACKGROUND: A classical problem in studying genome rearrangements is understanding the series of rearrangement events involved in transforming one genome into another in accordance with the parsimonious principle when two genomes with the same set of genes differ in gene order. The most studied event is the reversal, but an increasing number of reports have considered reversals along with other genome rearrangement events. Some recent studies have investigated the use of reversals and block-interchanges simultaneously with a weight proportion of 1:2. However, there has been less progress towards exploring additional combinations of weights. RESULTS: In this paper, we present several approaches to examine genome rearrangement problems by considering reversals and block-interchanges together using various weight assignments. An exact algorithm for the weight proportion of 1:2 is developed, and then, its idea is extended to design approximation algorithms for other weight assignments. The results of our simulations suggest that the performance of our approximation algorithm is superior to its theoretical expectation. CONCLUSION: If the weight of reversals is no more than that of block-interchanges, our algorithm provides an acceptable solution for the transformation of two permutations. Nevertheless whether there are more tractable results for studying the two events remains open. BioMed Central 2009-12-04 /pmc/articles/PMC2800848/ /pubmed/19958558 http://dx.doi.org/10.1186/1471-2105-10-398 Text en Copyright ©2009 Lin et al; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research article
Lin, Ying Chih
Lin, Chun-Yuan
Lin, Chunhung Richard
Sorting by reversals and block-interchanges with various weight assignments
title Sorting by reversals and block-interchanges with various weight assignments
title_full Sorting by reversals and block-interchanges with various weight assignments
title_fullStr Sorting by reversals and block-interchanges with various weight assignments
title_full_unstemmed Sorting by reversals and block-interchanges with various weight assignments
title_short Sorting by reversals and block-interchanges with various weight assignments
title_sort sorting by reversals and block-interchanges with various weight assignments
topic Research article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2800848/
https://www.ncbi.nlm.nih.gov/pubmed/19958558
http://dx.doi.org/10.1186/1471-2105-10-398
work_keys_str_mv AT linyingchih sortingbyreversalsandblockinterchangeswithvariousweightassignments
AT linchunyuan sortingbyreversalsandblockinterchangeswithvariousweightassignments
AT linchunhungrichard sortingbyreversalsandblockinterchangeswithvariousweightassignments