Week 15 - Consecutive ones property

Consider the sets being processed by the improved placement algorithm (DFS corresponds to the order they are given):

S1 = {1,4}
S2 = {1,3,5}
S3 = {3,2,5}
S4 = {1,3,2}

Now mark the CORRECT option that describes what happens when set S4 is added.

a) The C1P is destroyed because there is no empty neighbor to place the element {5} that was split from its class.
b) The C1P is destroyed because there is no empty neighbor to place the element {2} that was split from its class.
c) The C1P is destroyed because there is no empty neighbor to place the element {3} that was split from its class.
d) The C1P is destroyed because not all full classes are consecutive.
e) None of the above.

Original idea by: Raphael Cristofaro 

Week 14 - PQ-trees

Which of the bellow statements is INCORRECT?

a) Reading the leaves of a tree T from left to right yields its frontier, denoted by
FRONTIER(T).
b) A null tree (which has no nodes) is NOT considered as a PQ-tree.
c) A reversal of a P node is a equivalence transformation.
d) A reversal of a Q node is a equivalence transformation.
e) None of the above.

Translated by: Raphael Cristofaro
Original idea by: Moacy Barros Correia da Silva
(question number 071)

Week 13 - Dictionary order

As described by Benzer (1959), for n mutants, the probability that a randomly chosen, symmetric, binary matrix can be arranged in dictionary order is n!/2^{n(n- 1)/2}. Consider the following statements about the above expression and mark the INCORRECT one:

a) The number 2 raised by the expression n(n- 1)/2 relates to the matrix data alphabet (zeros and ones).
b) The number 2 raised by the expression n(n- 1)/2 relates to the matrix dimensions (columns and rows).
c) n! is the number of rearrangements that any given set of data may be subjected in one specific dimension (columns or rows).
d) n! is the number of possible row arrangements in satisfactory patterns.
e) None of the above.

Original idea by: Raphael Cristofaro

Week 12 - Unichromosomal genomes: block interchange

Select the alternative with the minimum number of block interchange operations that are needed to sort optimally the following genome:

+1 +8 +4 +7 +5 +2 +9 +6 +3 +10

a. 2.
b. 3.
c. 4.
d. 5.
e. None of the above.

Week 11 - Unichromossomal genomes, reversal

Given the permutation (0 2 4 3 5 1 6 8 7 9), consider the following statements according to the definitions by Bergeron (2005) on the Hannenhalli-Pevzner Theory.

I - This permutation contains only a simple hurdle, which is 2 4 3 5.
II - The whole permutation is a framed interval which also counts as a hurdle.
III - If the hurdle 2 4 3 5 is cutted, the permutation can be reduced in (0 2 1 3 5 4 6), which still has more than one hurdle.

Select the alternative with all the CORRECT statements and no others:

a. I.
b. II.
c. III.
d. II and III.
e. None of the above.

Original idea by: Raphael Cristofaro

Week 10 - Algebraic distance, definition

Given the graph α and its inverse, choose the CORRECT statement.

Image 1 - Cycle arrow notation from a) α and b) α^-1 (extracted from Kiltinen, 2003).

a. β = (2,4,5) is a cycle that divides both α and α^-1.
b. β = (4,2,1) is a cycle that divides α but not α^-1.
c. β = (1,3,5) is a cycle that divides α but not α^-1.
d. β = α^-1 is a cycle that divides α.
e. None of the above.

References: Kiltinen, John O. Oval Track And Other Permutation Puzzles: And Just Enough Group Theory To Solve Them. Washington, D.C.: Published and distributed by the Mathematical Association of America Press, 2003.

Original idea by: Raphael Cristofaro

Week 9 - Algebraic distance, permutations

About permutations, choose the CORRECT information.

a) Let α = (a b c) and β be a 2-cycle permutation containing a, b and c. The total number of cycles in αβ will be less than the number of cycles in β.
b) Let α = (a b) and β be any permutation. If a and b are in the same cycle on the cycle decomposition of β, then this cycle will be partitioned into two on the cycle decomposition of αβ.
c) Let α = (a b) and β be any permutation. If a and b are in separate cycles on the cycle decomposition of β, they will turn into a unique cycle on the decomposition of αβ.
d) Given a permutation α, its inverse α^-1 is obtained by the inverse of the cycle decomposition of each cycle in α.
e) None of the above.

Translated by: Raphael Cristofaro
Original idea by: Kaio Karam

Week 8 - Double-Cut-and-Join distance

About the end-capping phase (prior to DCJ steps), consider the following statements:

I - AA and BB paths are treated the same way when closed into cycles, with no arbitrary choices.
II - Before caps are incorporated into cycles, chromosomes are concatenated and additional operations made to prevent hurdles.
III - The expanded menu of end-capping operations avoid the need for extra precautions and saves running time to an O(n) complexity.

Select the alternative with all the correct statements and no others:
a. I.
b. II.
c. I and III.
d. II and III.
e. None of the above.

Original idea by: Raphael Cristofaro

Week 4 - Jukes-Cantor and Kimura Models

According to the model of DNA sequence evolution described by Kimura,
in the equation X(t) + Y(t) + 2 * Z(t) = 1, which sentence bellow is CORRECT?

a. Y(t) is the transition probability.
b. X(t) is the transversion probability.
c. Y(t) + 2 * Z(t) is the probability of having no changes.
d. The constant 2 is to consider the two different transition types (i.e., A<->G; C<->T).
e. None of the above.

Translated by: Raphael Cristofaro
Original idea by: Helder dos Santos Ribeiro

Week 3 - Sequence comparison

Which of the following statements is CORRECT?

a) Local alignments are most useful when the query set has similar sequences, it attempts to align every residue in those sequences.
b) Global alignments identify regions of similarity within long sequences that are often widely divergent overall.
c) Dynamic programming methods like the Needleman-Wunsch and the Smith-Waterman algorithms are the most useful to perform large-scale database searches.
d) Unlike dynamic programming methods, k-tuple methods like FASTA and BLAST are heuristics that guarantee to find an optimal alignment solution.
e) None of the above.

Original idea by: Raphael Cristofaro

Week 2 - Informatics Concepts

Consider the following graph properties and sign which statements are TRUE:

I - A Hamiltonian cycle can be converted to a Hamiltonian path by removing one of its edges.
II - A connected graph in which a vertex has odd degree can have an Eulerian cycle.
III - A cycle graph (a graph that consists of a single Eulerian and Hamiltonian cycle) that has an even number of vertices is bipartite.

a. I, II
b. I, III
c. II, III
d. AotA
e. NotA

Original idea by: Raphael Cristofaro