5. Iterate the previous exercise [finding a sorting operation] as many times as needed to find an optimal series of light algebraic sorting operations leading from π to σ. 'Light' operation here means an operation with weight 1 or less.
Exercises marked with (*) require further reading/search beyond the suggested texts.
5. Iterate the previous exercise [finding a sorting operation] as many times as needed to find an optimal series of light algebraic sorting operations leading from π to σ. 'Light' operation here means an operation with weight 1 or less.
Answer:
Adjacency algebraic representation of the genomes:
π = (-a +b) (-b -d) (+d +f) (-f -c) (+c +e) (-z +z)
σ = (-d +f) (-a -c) (+c -b) (+b +e)
We need to find a suitable divisor of σ π-1, then invert and conjugate it by π and see if they are disjoint. So σ π-1 must be calculated:
σ π-1 = (-a +e -b +f +d -d +c +b -c -f) (-z +z)
Choosing μ1 = (-a +e), we have π μ1 π-1 = (+b +c) disjoint from it and their product ρ1 = (-a +e) (+b +c) dividing σ π-1. Therefore, ρ1 is a sorting operation. Applying it to π we get:
π1 = ρ1 π = (-a +c) (-c -f) (+f +d) (-d -b) (+b +e) (-z +z)
σ π1-1 = (-a -b +f +d -d +c -c -f) (-z +z)
Choosing μ2 = (-a -b), we have π1 μ2 π1-1 = (+c -d) disjoint from it and their product ρ2 = (-a -b) (+c -d) dividing σ π1-1. Therefore, ρ2 is a sorting operation. Applying it to π1 we get:
π2 = ρ2 π1 = (-a -d) (+d +f) (-f -c) (+c -b) (+b +e) (-z +z)
σ π2-1 = (-a +f +d -d -c -f) (-z +z)
Choosing μ3 = (-a +f), we have π2 μ3 π2-1 = (-d +d) disjoint from it and their product ρ3 = (-a +f) (-d +d) dividing σ π2-1. Therefore, ρ3 is a sorting operation. Applying it to π2 we get:
π3 = ρ3 π2 = (-a +d) (-d +f) (-f -c) (+c -b) (+b +e) (-z +z)
σ π3-1 = (-a +d -c -f) (-z +z)
Choosing μ4 = (+d -c), we have π3 μ4 π3-1 = (-a -f) disjoint from it and their product ρ4 = (+d -c) (-a -f) dividing σ π3-1. Therefore, ρ4 is a sorting operation. Applying it to π3 we get:
π4 = ρ4 π1 = (-a -c) (+c -b) (+b +e) (-d +f) (-f +d) (-z +z)
σ π3-1 = (+d -f) (-z +z)
Now taking ρ5 = (+d -f) and ρ6 = (-z +z) we compete the sorting process. We used four operations of weight 1 and two operation of weight 1/2 for a total algebraic distance of 5.
© 2015 Joao Meidanis