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 breakpoint graph BP(π) of the permutation π, in which black edges are represented as solid lines and gray edges as dashed lines. The gray edge (4, 5) is oriented whereas (2, 3) is unoriented. In addition, there are two components C1 and C2, in which the former is a hurdle.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 1: The breakpoint graph BP(π) of the permutation π, in which black edges are represented as solid lines and gray edges as dashed lines. The gray edge (4, 5) is oriented whereas (2, 3) is unoriented. In addition, there are two components C1 and C2, in which the former is a hurdle.

Mentions: Let π be the permutation mentioned previously. The so-called breakpoint graph BP(π) is a powerful analysis tool for studying genome rearrangement problems, and is defined as an edge-colored graph with 2n + 2 vertices as follows: For 0 ≤ i ≤ n, π2i connects to π2i+1 by a black edge and 2i is joined to 2i + 1 by a gray edge (Figure 1). In BP(π), a gray edge (πi, πj) is said to be oriented if i + j is even, and otherwise it is unoriented. A cycle is said to be alternating if it contains alternating black and gray edges. Since the degree of each vertex is 2 (a black edge and a gray edge), the graph BP(π) can be uniquely decomposed into edge-disjoint and alternating cycles. In addition, a cycle is oriented as long as it has an oriented gray edge, otherwise, it is unoriented. The length of a cycle is the number of black (or equivalently, gray) edges it contains. We use l-cycle to denote an alternating cycle with length l, and c(π) to denote the number of cycles in BP(π), e.g., in Figure 1, c(π) = 2: one is a 5-cycle and the other is a 3-cycle. Note that c(π) = n + 1 if and only if π = I.


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

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

The breakpoint graph BP(π) of the permutation π, in which black edges are represented as solid lines and gray edges as dashed lines. The gray edge (4, 5) is oriented whereas (2, 3) is unoriented. In addition, there are two components C1 and C2, in which the former is a hurdle.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 1: The breakpoint graph BP(π) of the permutation π, in which black edges are represented as solid lines and gray edges as dashed lines. The gray edge (4, 5) is oriented whereas (2, 3) is unoriented. In addition, there are two components C1 and C2, in which the former is a hurdle.
Mentions: Let π be the permutation mentioned previously. The so-called breakpoint graph BP(π) is a powerful analysis tool for studying genome rearrangement problems, and is defined as an edge-colored graph with 2n + 2 vertices as follows: For 0 ≤ i ≤ n, π2i connects to π2i+1 by a black edge and 2i is joined to 2i + 1 by a gray edge (Figure 1). In BP(π), a gray edge (πi, πj) is said to be oriented if i + j is even, and otherwise it is unoriented. A cycle is said to be alternating if it contains alternating black and gray edges. Since the degree of each vertex is 2 (a black edge and a gray edge), the graph BP(π) can be uniquely decomposed into edge-disjoint and alternating cycles. In addition, a cycle is oriented as long as it has an oriented gray edge, otherwise, it is unoriented. The length of a cycle is the number of black (or equivalently, gray) edges it contains. We use l-cycle to denote an alternating cycle with length l, and c(π) to denote the number of cycles in BP(π), e.g., in Figure 1, c(π) = 2: one is a 5-cycle and the other is a 3-cycle. Note that c(π) = n + 1 if and only if π = I.

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