Question 12. 

Considering one of the innovations of the algorithm presented in "Building PQR trees in almost-linear time", published by Telles and Meidanis in 2005, it is correct to say that it:

A) Substitutes the comparing by patterns in PQ trees for a simpler algorithm, which relies only in the types of gray nodes and the LCA (Least Common Ancestor).
B) Separates the construction of PQR trees in two distinct parts, represented by the BUBBLE and REDUCE algorithms.
C) Makes an adaptation to the "Divide and Conquer" technique for dividing the starting tree into smaller sub-trees.
D) Uses a hash algorithm to reduce the amount of information related to white nodes.
E) None of the above.

(Original idea by: Adriano Batista Prieto || Translated by: Celso A. W. Santos)

Question 11. 

Consider the following genome below:

+1 +6 +2 +4 +7 +5 +3

This genome can be sorted with a certain amount of block interchanges. According to the algorithm, which are the values for X when the sorting through block interchanges is applied, as well as the resulting Block Interchange Distance (BID)? (Consider X_i as the i-eth iteration of the sorting algorithm).

A) X₁ = 1; X₂ = 3; X₃ = 4; X₄ = 6. BID = 4.
B) X₁ = 2; X₂ = 3; X₃ = 4. BID = 3.
C) X₁ = 2; X₂ = 3; X₃ = 4; X₄ = 5. BID = 2.
D) X₁ = 2; X₂ = 4; X₃ = 5. BID = 3.
E) None of the above.

(Original idea by: Celso A. W. Santos)

Question 10. 

Consider the following adjacency graph:

The correct representation for genomes A and B and the DCJ distance between them are:

A) DCJ_dist = 3


B) DCJ_dist = 4
 

C)  DCJ_dist = 4


D) DCJ_dist = 5
 
E) None of the above.

(Original idea by: Celso A. W. Santos)

Question 9. 

Consider the following Genome below:

The correct π_chr for for this genome is:
A) (C, -B, A) (F, G) (D, -E)
B) (-A, C, -B) (-F, G) (D, E)
C) (A, C, B) (F, G) (-E, D)
D) (B, A, C) (G, F) (-E, D)
E) None of the above.

(Original idea by: Celso A. W. Santos)