Question 15. 

Consider the following data structure representation for the following sets S1 to S4, added in DFS order:


If it was now turn to analyse S5 = {3, 4, 8, 9}. By adding this set to the data structure:A) ... the C1P would be destroyed due to having a new class but not a full extremity in the path to place it.
B) ... the C1P would hold true.
C) ... the C1P would be destroyed due to not having all full classes consecutive.
D) ... the C1P would be destroyed due to not having an empty neighbour to place an uncoloured subclass.
E) None of the above.

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

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)

Question 4. 

According to D. Durand's "Markov models for sequence evolution" lecture notes, these models of sequence evolution are used to answer a wide range of questions, except:

A) Simulating sequence evolution.
B) Estimating the likelihood of observing a pair of aligned nucleotides, given a phylogenetic model.
C) Estimating rates of evolution.
D) Deriving substitution scoring matrices.
E) None of the above.

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

Question 2. 

Suppose a known problem X with unknown complexity. We know that we can verify a given instance of X in polynomial time. Suppose, also, that it is able to reduce a known NP-complete problem to X in polynomial time. If, after some research, we were to discover that there is a polynomial time algorithm that solves problem X, then... 
A) X, which is NP-hard, proves that P == NP. 
B) X, which is NP-hard, proves that P != NP. 
C) X, which is NP-complete, proves that P == NP. 
D) X, which is NP-complete, proves that P != NP. 
E) None of the above.