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

The reversal specified by a pair of blue parentheses comes from an oriented gray edge (πi, πj), in which i and j are even.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 5: The reversal specified by a pair of blue parentheses comes from an oriented gray edge (πi, πj), in which i and j are even.

Mentions: Let oge = (πi, πj) be an oriented gray edge, and roge be a reversal defined by two black edges linking πi and πj. Then, we immediately know that i + j is even, and hence, both i and j are either even or odd. The reversal roge, irrespective of "even" or "odd" case, results in breaking a cycle into two smaller ones, i.e., = 1, as demonstrated in Figure 5. Notice that an oge can correspond to a reversal having Δcr = 1, and it is false conversely, i.e., not all optimal reversals can map to oriented gray edges; take = (-1, -2, -3) and r(2, 2) as an example. Besides, a reversal roge complements the gray edges overlapping with oge. In other words, after applying roge, oriented gray edges overlapping with oge become unoriented and vice versa. The heuristic used to compute P(oge) and select the maximum results from which we want to leave as many unoriented gray edges as possible after performing a reversal. Then, the algorithm is summarized as follows:


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

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

The reversal specified by a pair of blue parentheses comes from an oriented gray edge (πi, πj), in which i and j are even.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 5: The reversal specified by a pair of blue parentheses comes from an oriented gray edge (πi, πj), in which i and j are even.
Mentions: Let oge = (πi, πj) be an oriented gray edge, and roge be a reversal defined by two black edges linking πi and πj. Then, we immediately know that i + j is even, and hence, both i and j are either even or odd. The reversal roge, irrespective of "even" or "odd" case, results in breaking a cycle into two smaller ones, i.e., = 1, as demonstrated in Figure 5. Notice that an oge can correspond to a reversal having Δcr = 1, and it is false conversely, i.e., not all optimal reversals can map to oriented gray edges; take = (-1, -2, -3) and r(2, 2) as an example. Besides, a reversal roge complements the gray edges overlapping with oge. In other words, after applying roge, oriented gray edges overlapping with oge become unoriented and vice versa. The heuristic used to compute P(oge) and select the maximum results from which we want to leave as many unoriented gray edges as possible after performing a reversal. Then, the algorithm is summarized as follows:

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