Bioinformatics Multiple Choice Questions on “Heuristic Algorithms”.
1. Which of the following is untrue regarding the Progressive Alignment Method? Answer: D 2. Clustal is a progressive multiple alignment program available either as a stand-alone or on-line program. Answer: A 3. Which of the following is untrue regarding the progressive alignment method? Answer: c 4. Which of the following is not a drawback of the progressive alignment method? Answer: c 5. Which of the following is untrue regarding T-Coffee? : c 6. Which of the following is untrue about iterative approach? Answer: D 7. Which of the following is untrue about PRRN? Answer: D 8. The major drawback of the progressive and iterative alignment strategies is that they are largely global alignment based and may therefore fail to recognize conserved domains and motifs among highly divergent sequences of varying lengths. Answer: A 9. Which of the following is untrue about DIALIGN2? Answer: B 10. Match-Box compares segments of some of the nine residues of possible Pair wise alignments. Answer: b
A. Progressive alignment depends on the stepwise assembly of multiple alignments and is heuristic in nature
B. It speeds up the alignment of multiple sequences through a multistep process
C. It first conducts pair wise alignments for each possible pair of sequences using the Needleman–Wunsch global alignment method and records these similarity scores from the pair wise comparisons
D. Its drawback is it slows down the alignment of multiple sequences through a single step process
Explanation: Progressive alignment speeds up the alignment of multiple sequences through a multistep process further, the scores can either be percent identity or similarity scores based on a particular substitution matrix. Both scores correlate with the evolutionary distances between sequences.
A. True
B. False
Explanation: Probably the most well-known progressive alignment program is Clustal. The stand-alone program, which runs on UNIX and Macintosh, has two variants, Clustal W and Clustal X. The W version provides a simple text-based interface and the X version provides a more user-friendly graphical interface.
A. The program also applies a weighting scheme to increase the reliability of aligning divergent sequences (sequences with less than 25% identity)
B. The progress is done by down weighting redundant and closely related groups of sequences in the alignment by a certain factor
C. This scheme is useful in enhancing similar sequences from dominating the alignment
D. This scheme is useful in enhancing similar sequences from dominating the alignment
Explanation: This scheme is useful in enhancing similar sequences from dominating the alignment. Further, the weight factor for each sequence is determined by its branch length on the guide tree. The branch lengths are normalized by how many times sequences share a basal branch from the root of the tree.
A. The progressive alignment method is not suitable for comparing sequences of different lengths because it is a global alignment–based method
B. In this method the use of affine gap penalties, long gaps are not allowed, and, in some cases, this may limit the accuracy of the method
C. In this method the use of affine gap penalties, long gaps is allowed, and, in some cases, this may limit the accuracy of the method
D. The final alignment result is also influenced by the order of sequence addition
Explanation: Another major limitation is the “greedy” nature of the algorithm: it depends on initial pair wise alignment. Once gaps introduced in the early steps of alignment, they are fixed. The final alignment could be far from optimal. The problem can be more glaring when dealing with divergent sequences.
A. It stands for Tree-based Consistency Objective Function for alignment Evaluation
B. It performs progressive sequence alignments as in Clustal.
C. The global pair wise alignment is not performed using the Clustal program.
D. The local pair wise alignment is generated by the Lalign program, from which the top ten scored alignments are selected
Explanation: The global pair wise alignment is performed using the Clustal program. The main difference is that, in processing a query, T-Coffee performs both global and local pair wise alignment for all possible pairs involved. The collection of local and global sequence alignments is pooled to form a library. The consistency of the alignments is evaluated.
A. The iterative approach is based on the idea that an optimal solution can be found by repeatedly modifying existing suboptimal solutions
B. Because the order of the sequences used for alignment is different in each iteration
C. This method is also heuristic in nature and does not have guarantees for finding the optimal alignment
D. This method is not based on heuristic methods
Explanation: This method is based on heuristic methods. The procedure starts by producing a low-quality alignment and gradually improves it by iterative realignment through well-defined procedures until no more improvements in the alignment scores can be achieved.
A. PRRN is a web-based program that uses a double nested iterative strategy for multiple alignment
B. It performs multiple alignments through two sets of iterations: inner iteration and outer iteration
C. In the outer iteration, an initial random alignment is generated that is used to derive a UPGMA tree
D. In the inner iteration, the sequences are randomly divided into multiple groups
Explanation: In the inner iteration, the sequences are randomly divided into two groups. Randomized alignment is used for each group in the initial cycle, after which the alignment positions in each group are fixed. The two groups, each treated as a single sequence, are then aligned to each other using global dynamic programming. The process is repeated through many cycles until the total SP score no longer increases. At this point, the resulting alignment is used to construct a new UPGMA tree.
A. True
B. False
Explanation: For such divergent sequences that share only regional similarities, a local alignment based approach has to be used. The strategy identifies a block of ungapped alignment shared by all the sequences, hence, the block-based local alignment strategy.
A. It is a web based program designed to detect local similarities
B. It is designed to detect global similarities
C. It does not apply gap penalties and thus is not sensitive to long gaps
D. The method breaks each of the sequences down to smaller segments and performs all possible pair wise alignments between the segments
Explanation: High-scoring segments, called blocks, among different sequences are then compiled in a progressive manner to assemble a full multiple alignment. It places emphasis on block-to-block comparison rather than residue-to-residue comparison. The sequence regions between the blocks are left unaligned. The program has been shown to be especially suitable for aligning divergent sequences with only local similarity.
A. True
B. False
Explanation: Match-Box compares segments of every nine residues of all possible pair wise alignments. It is a web-based server that also aims to identify conserved blocks (or boxes) among sequences. The program compares segments of every nine residues of all possible pair wise alignments. If the similarity of particular segments is above a certain threshold across all sequences, they are used as an anchor to assemble multiple alignments; residues between blocks are unaligned.