010-2011

MO640 - Multiple-choice question

Consider the following sequences:  s = AACT  and  t = GAGG . If we apply the basic global alignment algorithm on these sequences, with weights match = 1, mismatch = -1 and gap = -2, where s occupies the first column and t the first row, what are the values of the last row and the last column of the matrix?

a. Row: -8,-7,-3,-2,-1 ; Column: -8,-5,-4,-3,-2

b. Row: -8,-7,-3,-2,-1 ; Column: -8,-5,-3,-2,-1

c. Row: -8,-7,-4,-3,-2 ; Column: -8,-5,-4,-3,-2

d. Row: -8,-7,-4,-3,-1 ; Column: -8,-5,-3,-2,-1

e. None of the above

 

Original idea by: Wilson Vendramel

Translation help by: Shagalí Huanca Vargas

035-2008

MO640 - Multiple-choice question

Which of the following modifications do not need to be made to the global alignment algorithm to transform it into the local alignment algorithm?

1. Initialize with zeros the first column and the first row of the matrix.
2. Stop the reconstruction of a local alignment as soon as a 0 is found in the matrix.
3. Do not let the matrix values become negative; if the maximum value is negative, it should be replaced by 0.
4. Find the highest value on the entire matrix to obtain the similarity and use its position as a starting point for reconstruction of an optimal alignment.
5. None of the above.

Original idea by: Filipe Benevides Netto
Translation help by: Leandro José de Bortoli. 

011-2015

MO640 - Multiple-choice question

Which of the following statements is CORRECT?

a) Local alignments are most useful when we have similar sequences and need to align every residue in these 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 reasonable choices 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.
e) None of the above.

Original idea by: Raphael Cristofaro

010-2015

MO640 - Multiple-choice question

During the sequencing of an organism, a researcher found three different base sequences for a certain region of interest, aligned as follows:

Sequence 1: AA-AGCCACGGGG-AAGCTGACGTCCA

Sequence 2: AA-AGCCA-GC-GCAAGCTGACGTCCA

Sequence 3: AATAGCCACGGGGCAAGCTGACG-CCA

Which of the alternatives below is most likely the original sequence of this region?

 

a) AA-AGCCA-GCG-CAAGCTGACGCCCA

b) AATAGCCACGGGGCAAGCTGACGTCCA

c) AAAGCCACGGGGCAAGCTGACCTCCA

d) AAAGCCAGGGAAGCTGACCTCAAA

e) None of the above

 

Original idea by: Mario Akita

009-2015

MO640 - Multiple-choice question

Consider the following alignments on DNA sequences, where matches, mismatches, and spaces are shown by '|', '.', and '-', respectively:

First Alignment:

5' ATTACCTAGATTACTTACGGATCAGGTACTTTAGAGGCTTGCTT 3' 
             |-|||.||||||.|||||||||||||||
          5' T-ACTCACGGATGAGGTACTTTAGAGGC 3'

Second Alignment:

5' ACTTCTAGATTACTTACGGATCAGGTACTTTAGAGGCTTGCAACCT 3'
   |||||||||||----|||||||--||||||||||||||.|||||||
5' ACTTCTAGATT----ACGGATC--GTACTTTAGAGGCTAGCAACCT 3'

and the following statements:

I. The first alignment is a global alignment.
II. The second alignment is both local and global.
III. The basic dynamic programming algorithm comparing two
sequences with same length n runs in time O(n²) .


Which alternative is true?

a. statements I, II, and III are correct
b. only statements I and II are correct
c. only statements I and III are correct
d. only statements II and III are correct
e. None of the above

Original idea by: Jessica Akemi Matsuoka

013-2004

MO640 - Multiple-choice question

Considering the class of interval graphs, which alternative is correct:

1. No polynomial-time algorithm is known for deciding whether a given graph is an interval graph.
2. Every induced subgraph of an interval graph is itself an interval graph.
3. If an induced subgraph of a graph G is an interval graph, then G is also an interval graph.
4. The graph C₄ (cycle with 4 vertices) belongs to this class.
5. None of the abova

Original idea by: Marília Felippe Chiozo

010-2004

MO640 - Multiple-choice question

Let G be an acyclic directed graph. The strongly connected components of G are:

1. vertices.
   
2. nontrivial trees, that is, trees with 2 or more vertices.
   
3. cicles, where the edge orientations are disregarded.
   
4. paths with at least one edge.
   
5. None of the above

Original idea by: Cleber Valgas Gomes Mira