Objective: To familiarize the student with genome arrangements.

Given an orientation, a , determine the cycles (good, bad, or unclassified), and, in choosing one good cycle to test, check which edges of this cycle would be good choices to reverse. This is similar to the discussions in class, material given, and chapter 7 of the text.

Input: a

Output:

• cycles
• classification of cycles (good, bad, or unclassified - if there are no good cycles, program should terminate)
• edges in one of the good cycles
• reversals of each of these edges
• cycles produced after reversal
• determination of good choice for reversal
• any other necessary information

Submit:

1. Algorithm
2. Hard copy of program & program on disk.
3. Three different runs - input and output. Make sure that only one of your runs terminates early.

You must run your program for the class on April, so make sure that it is executing properly on a Howard University system. You may program this in any language.

Example:

Given input a = (L, +3, -3, -4, +4, +1, -1, +2, -2, -5, +5, R).

Cycles:

A = (L, +3, -4, -3, +2, -1), proper, good

B = (+4, +1, -2, -5), proper, bad

C = (R, +5), not proper, unclassified

Edges in good cycle:

a = (-3, -4)

b = (L, +3)

c = (-1, +2)

Testing edges a and b

New orientation = (L, -3, +3, -4, +4, +1, -1, +2, -2, -5, +5, R)

Cycles:

A = (L, -3, +2, -1), proper, good

B = (+3, -4), not proper, unclassified

C = (R, +5), not proper, unclassified

Result: good choice for reversal

Testing edges a and c

New orientation = (L, +3, -3, -1, +1, +4, -4, +2, -2, -5, +5, R)

Cycles:

A = (L, +3, -4, +2, -3, -1), proper, good

B = (+1, +4, -5, -2), proper, good

C = (R, +5), not proper, unclassified

Result: good choice for reversal

Testing edges b and c

New orientation = (L, -1, +1, +4, -4, -3, +3, +2, -2, -5, +5, R)

Cycles:

A = (+1, +4, -5, -2), proper, good

B = (-4, -3, +2, +3), proper, good

C = (R, +5), not proper, unclassified

D = (-1, L), not proper, unclassified

Result: good choice for reversal