Single Tandem Halving by Block Interchange - Biomedical Engineering Systems and Technologies - page 151

Algorithm 1. Reconstruction of a single tandem duplicated genome
1: while G contains more than 3 markers do
2: Construct I ( G )
3: Pick a smallest interval I ( ab ) that is not of type 2 in I ( G )
4: Find an interval I ( xy ) in I ( G ) compatible with I ( ab )
5: Perform the BI equivalent to DCJ ( ab ) followed by DCJ ( xy )
6: Reduce G
7: end while
8: if G contains 2 or 3 markers then
9: Find the last BI operation and perform it
10: end if

Proof. Building ( G ) and finding two compatible intervals can be done in O ( n ) time

and space complexity. It follows that the while loop in the algorithm can be computed
in O ( n 2 ) time and space complexity.
Finding and performing the last BI operation when 2

I

≤ n ≤ 3 can be done in

constant time and space complexity.
Moreover, all BI operations, possibly excluding the last one, are computed as pairs of
compatible intervals, ie. pairs of sorting DCJ operations, which ensures that the length
of the scenario is

n − C

2

.

Corollary 1. Any BI scenario computed by Algorithm 1 is also a most parsimonious
DCJ scenario, twice as long since a BI is equivalent to 2 DCJ.

An example of scenario is shown in figure 3.

d DCJ = n − EC − OP
2

=4

n =5; EC =1; d =4
( ◦ 1 233 54 124 5 ◦ )

excision

n =5; EC =2; d =3
( ◦ 1 2 3 3124 5 ◦ )(5 4)

=BI( ◦ 1 2 3 3 5 4 124 5 ◦ )

reintegration

n =5; EC =3; d =2
( ◦ 1 2453 3124 5 ◦ )

excision

n =5; EC =4; d =1
(1 245 3) ( ◦ 3124 5 ◦ )

=BI( ◦ 1 245 3 3124 5 ◦ )

reintegration

n =5; EC =5; d =0
( ◦ 3 1 2453124 5 ◦ )

d BI = d DCJ
2

=2

Fig. 3. A BI scenario computed by algorithm 1