Limits...
Sorting by reversals and block-interchanges with various weight assignments.

Lin YC, Lin CY, Lin CR - BMC Bioinformatics (2009)

Bottom Line: 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.Nevertheless whether there are more tractable results for studying the two events remains open.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan. yclin@cse.nsysu.edu.tw

ABSTRACT

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.

Show MeSH

Related in: MedlinePlus

Two unoriented gray edges g = (πi, πk) and f = (πj, πl) overlapping in a component are in the same cycle with (a) j = i + 1 and (b) j >i + 1, whereas (c) g and f are in different cycles.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC2800848&req=5

Figure 3: Two unoriented gray edges g = (πi, πk) and f = (πj, πl) overlapping in a component are in the same cycle with (a) j = i + 1 and (b) j >i + 1, whereas (c) g and f are in different cycles.

Mentions: (1) j = i + 1, i.e., there is a black edge linking πi and πj (Figure 3a). Using the assumption of k < l, and that k is odd and l is even, there is no black edge between πk and πl. Therefore, we use the three black edges, (πi, πj), (a, πk), and (πl, b) to determine the block-interchange bi(j, k - 1, k, l). After performing it, the number of cycles is increased by two (Figure 3a), i.e., Δcbi = 2.


Sorting by reversals and block-interchanges with various weight assignments.

Lin YC, Lin CY, Lin CR - BMC Bioinformatics (2009)

Two unoriented gray edges g = (πi, πk) and f = (πj, πl) overlapping in a component are in the same cycle with (a) j = i + 1 and (b) j >i + 1, whereas (c) g and f are in different cycles.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC2800848&req=5

Figure 3: Two unoriented gray edges g = (πi, πk) and f = (πj, πl) overlapping in a component are in the same cycle with (a) j = i + 1 and (b) j >i + 1, whereas (c) g and f are in different cycles.
Mentions: (1) j = i + 1, i.e., there is a black edge linking πi and πj (Figure 3a). Using the assumption of k < l, and that k is odd and l is even, there is no black edge between πk and πl. Therefore, we use the three black edges, (πi, πj), (a, πk), and (πl, b) to determine the block-interchange bi(j, k - 1, k, l). After performing it, the number of cycles is increased by two (Figure 3a), i.e., Δcbi = 2.

Bottom Line: 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.Nevertheless whether there are more tractable results for studying the two events remains open.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan. yclin@cse.nsysu.edu.tw

ABSTRACT

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.

Show MeSH
Related in: MedlinePlus