Homework 2

HomeWork #2

Q1. Determine the alignment score for each of the following:

global alignment: match=1, mismatch = 0 and gap = -1

--TCTGTACGCGATCATGT
TAGC-GTCCGATAT-A---

global alignment: match=1, mismatch=-1, affine gap: -2 for start and -1 for extension

AGATAGAAACTGATATATA
AG---AAAACAGAGT----

semiglobal alignment: match=1, mismatch=-1, affine gap: -2 for starting, -1 for extension

AGATAGAAACTGATATATA
AG---AAAACAGAGT----

Q2. Calculate the log odds and odds scores of a sequence alignment using the BLOSUM scoring matrix approach.

In one column of an alignment of a set of related, similar sequences, amino acid D changes to amino acid E at a frequency of 0.10, and the number of times this change is expected based on the number of occurrences of D and E in the column is 0.05.

What is the odds of finding a D to E substitution in an alignment?

What is the log odds score for the D to E substitution in bits? (Note: log₂ = natural log / 0.693.)

What would be the entry in the BLOSUM amino acid scoring matrix for this substitution?

In the same column, D does not change at all at a frequency 0.80, and the expected frequency of D not changing is 0.10. Calculate the corresponding log odds score and the BLOSUM entry for D not changing.

Use the BLOSUM scores from above to calculate the log odds and odds score of a simple sequence alignment.

What is the log odds score of the following alignment in bits?
DEDEDEDE
DDDDDDDD
What is the odds score of the above alignment?

Q3. Assume that you are given the following block (local alignment) of 12 sequences:

WWYIR
WFYVR
WYYVR
WYFIR
WYYTR
WFYKR
WFYKR
WYYVR
WYYVR
WFYTR
WFYTR
WWYVR

Assume we cluster any sequence that occurs two or more times (i.e., cluster threshold 2/12 = 1/6). Compute the BLOSUM matrix from the clustered block. Express it in half bits.

Q4. Compare the alignment scores obtained with small and large gap penalties in the following example.
For this question, use the program LALIGN on the University of Virginia FASTA server. This program aligns sequences by a local dynamic programming algorithm and includes end gap penalties. LALIGN produces as many different alignments as specified, with no two alignments including a match of the same two sequence positions.

Two sequences are provided in FASTA format: RECA from the bacterium E. coli and RAD51 from yeast. These proteins have the same function; i.e., promoting the pairing of homologous single-stranded DNAs. They almost certainly have the same three-dimensional structure but have diverged enough that they are difficult to align.

Use LALIGN to align the above two sequences with gap penalties of -12 and -2. Note the length of the alignment, the % identity, and the score of the alignment.
Repeat the alignment with gap penalties of -5 and -1 and note the features of the alignment.
Describe what happened when the gap penalties were reduced. Which of these alignments look like a local alignment and which like a global alignment?

Q5. Assume that you are given the following two groups of aligned sequences. Use a global pairwise dynamic programming method to align these two groups using the sum of pairs scoring method (use match=1, mismatch=0, gap = -1):

Group 1: AC--TCG
         ACAGTAG

Group 2: AGACGTG
         --ACGT-

Q6. Assume we are using the tunneling method to search only within a specified region for a multiple sequence alignment. Let there be three sequences of lengths 3, 4 and 5. Assuming a tunnel of width 2 around the main diagonal, use the projection approach to calculate if the cell (1,3,4) is within the tunnel. Show all calculation.

Q7. Using the CLUSTALW program, align the provided set of proteins in the RAD51-RECA group. These proteins
promote homologous DNA strand interactions during genetic recombination between DNA molecules.
CLUSTALW is available for PCs and also on a Web site at EBI. Copy and paste the sequence file into the CLUSTALW data window (sequence is in FASTA format). Just use the default conditions provided by the program.

Note the two kinds of multiple sequence alignment output formats. One is the ALN format with numbers, and the
second is the FASTA format with the aligned sequences joined end to end in FASTA format, with gaps in each sequence corresponding to the alignmnent.

Q8. When a multiple sequence alignment can be made, then we can pick out the most conserved regions (motifs), make a scoring matrix, and search for other sequences that have this same motif. The matrix will take into account the variation found in the sequences. We will make a position-specific scoring matrix (also called a PSSM or weight matrix) to a part of a given multiple sequence alignment and using the matrix to scan a sequence.

Here is a table showing the frequency of each base in an alignment that is 4 bases long.

Assuming that the background frequency is 0.25 for each base, calculate a log odds score for each table position; i.e., log to the base 2 of the ratio of each observed value to the expected frequency.
Aligning the matrix with each position in the following sequence starting at position 1, 2, ..., calculate the log odds score for the matrix to match that position.

Sequence: TGAGCTAA

Now convert the alignment scores to odds scores, sum them, and calculate the probability of the best matching position.

Q9. Analyze the following 10 DNA sequences by the expectation maximization algorithm. Assume that the background base frequencies are each 0.25 and that the middle 3 positions are a motif. The size of the motif is an informed guess based on a molecular model, and the alignment of the sequences is also an informed guess.

sequence 1   C CAG A
sequence 2   G TTA A
sequence 3   G TAC C
sequence 4   T TAT T
sequence 5   C AGA T
sequence 6   T TTT G
sequence 7   A TAC T
sequence 8   C TAT G
sequence 9   A GCT C
sequence 10  G TAG A

Make a table with 3 columns (position in motif) and 4 rows (1 for each base). Calculate the observed frequency of each base at each of the 3 positions.
Using the frequencies in the column tables, and the background frequencies, calculate the likelihood of finding the motif at each of the possible locations in sequence 5.
Calculate the probability of finding the motif at each position in sequence 5.
Calculate what change will be made to the base count in each column of the motif table as a result of matching the motif to the first position in sequence 5.
What other steps are taken to update or maximize the table values?

Q10. MEME is a server that will take as input a set of sequences and find alignment by the expectation maximization method. Paste the same unaligned RECA-RAD51 sequences (NOT the aligned ones) into the window and use the defaults provided by the program. Try with other options like "optimal" number of motifs, etc. Summarize your output. List all motifs (do not cut an paste all the output, just the relevant parts).

Q11. Analyze the following 10 DNA sequences for a conserved pattern by the Gibbs sampling algorithm.

sequence 1   C CAG A
sequence 2   G TTA A
sequence 3   G TAC C
sequence 4   T TAT T
sequence 5   C AGA T
sequence 6   T TTT G
sequence 7   A TAC T
sequence 8   C TAT G
sequence 9   A GCT C
sequence 10  G TAG A

Assuming that the background base frequencies are 0.25, calculate a log odds matrix for the central three positions.
Assuming that another sequence GTTTG is the left-out sequence, slide the log odds matrix along the left-out sequence and find the log odds score at each of three possible positions.
Change each log odds score to an odds score and sum the odds scores. Calculate the probability of a match at each position in the left-out sequence. (Odds score = 2^{log odds score}.)

Q12. Consider the hidden Markov Model (HMM) below:

Red square, match state; green diamond, insert state; blue circle, delete state. Arrows indicate probability of going from one state to the next.

Calculate the probability of the sequence TAG by following a path through the model starting at Begin, going through each of the three match states (red squares), and ending at End.
Repeat part 1 for a path that, starting at Begin, goes first to the first insert state (green diamond), then to a match state (red square), then to a delete state (blue circle, probability 1 for any character in this state), then to a match state and finishing at End.
Which of the two paths is the more probable one, and what is the ratio of the probability of the higher to the lower one? The highest scoring path is the best alignment of the sequence with the model and for real sequences is found by dynamic programming.
Change all the values in each of the states to log odds scores, assuming that the frequency of each base is 0.25. Also change the transition probabilities to log odds; i.e., log to the base 2 of the ratio of observed transition probability to background probability. (Note: Transition background is an equal probability of making a transition to each subsequent state and will be calculated by dividing 1 by the number of possible transitions from each state; i.e., the background probability will be one of 1/2=0.5, 1/3=0.33, or 1/1). Now calculate the probability in part 1 as a log odds score.