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...
Autores principales: | , , |
---|---|
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 |