# Algorithms for DNA Sequencing Coursera Quiz Answers

## Get All Weeks Algorithms for DNA Sequencing Coursera Quiz Answers

### Week 1

#### Quiz 1: Module 1

Q1. Which of the following is not a suffix of CATATTAC?

• CAT
• TATTAC
• TAC
• C

Q2. What’s the longest prefix of CACACTGCACAC that is also a suffix?

• CACAC
• C
• CACACTG
• CAC

Q3. Which of the following is not a substring of GCTCAGCGGGGCA?

• GCC
• GCT
• GCA
• GCG

Q4. Starting around 2007, the cost of DNA sequencing started to decrease rapidly because more laboratories started to use:

• Sanger sequencing
• Double sequencing
• Second-generation sequencing
• DNA microarrays

Q5. Which of the following pieces of information is not included in a sequencing read in the FASTQ format:

• The sequence of base qualities corresponding to the bases
• A “name” for the read
• The sequence of bases that make up the read
• Which chromosome the read originated from

Q6. If read alignment is like “looking for a needle in a haystack,” then the “haystack” is the:

• Gene database
• Reference genome
• Sequencer

Q7. The Human Genome Project built the initial “draft” sequence of the human genome, starting from sequencing reads. The computational problem they had to solve was the:

• prime factorization problem
• de novo shutgun assembly problem
• gene finding problem
• read alignment problem

Q8. If the length of the pattern is x and the length of the text is y, the minimum possible number of character comparisons performed by the naive exact matching algorithm is:

• y – x + 1
• xy
• x + y
• x(y – x + 1)

Q9. If the length of the pattern is x and the length of the text is y, the maximum possible number of character comparisons performed by the naive exact matching algorithm is:

• x + y
• xy
• y – x + 1
• x(y – x + 1)

Q10. Say we have a function that generates a random DNA string, i.e. the kind of string we would get by rolling a 4-sided die (A/C/G/T) over and over. We use the function to generate a random pattern P of length 20 and a random text T of length 100. Now we run the naive exact matching algorithm to find matches of P within T. We expect the total number of character comparisons we perform to be closer to the…

• maximum possible
• minimum possible

#### Quiz 2: Programming Homework 1

Q1. How many times does \verb|AGGT|AGGT or its reverse complement (\verb|ACCT|ACCT) occur in the lambda virus genome? E.g. if \verb|AGGT|AGGT occurs 10 times and \verb|ACCT|ACCT occurs 12 times, you should report 22.

`Enter answer here`

Q2. How many times does \verb|TTAA|TTAA or its reverse complement occur in the lambda virus genome?

Hint: \verb|TTAA|TTAA and its reverse complement are equal, so remember not to double count.

`Enter answer here`

Q3. What is the offset of the leftmost occurrence of \verb|ACTAAGT|ACTAAGT or its reverse complement in the Lambda virus genome? E.g. if the leftmost occurrence of \verb|ACTAAGT|ACTAAGT is at offset 40 (0-based) and the leftmost occurrence of its reverse complement \verb|ACTTAGT|ACTTAGT is at offset 29, then report 29.

Q4. What is the offset of the leftmost occurrence of \verb|AGTCGA|AGTCGA or its reverse complement in the Lambda virus genome?

`Enter answer here`

Q5. As we will discuss, sometimes we would like to find approximate matches for P in T. That is, we want to find occurrences with one or more differences.

For Questions 5 and 6, make a new version of the \verb|naive|naive function called \verb|naive_2mm|naive_2mm that allows up to 2 mismatches per occurrence. Unlike for the previous questions, do not consider the reverse complement here. We’re looking for approximate matches for P itself, not its reverse complement.

For example, \verb|ACTTTA|ACTTTA occurs twice in \verb|ACTTACTTGATAAAGT|ACTTACTTGATAAAGT, once at offset 0 with 2 mismatches, and once at offset 4 with 1 mismatch. So \verb|naive_2mm(‘ACTTTA’, ‘ACTTACTTGATAAAGT’)|naive_2mm(’ACTTTA’, ’ACTTACTTGATAAAGT’) should return the list \verb|[0, 4]|[0, 4].

Hint: See this notebook for a few examples you can use to test your \verb|naive_2mm|naive_2mm function.

How many times does \verb|TTCAAGCC|TTCAAGCC occur in the Lambda virus genome when allowing up to 2 mismatches?

`Enter answer here`

Q6. What is the offset of the leftmost occurrence of \verb|AGGAGGTT|AGGAGGTT in the Lambda virus genome when allowing up to 2 mismatches?

Q7. Finally, download and parse the provided FASTQ file containing real DNA sequencing reads derived from a human:

Note that the file has many reads in it and you should examine all of them together when answering this question. The reads are taken from this study:

Ajay, S. S., Parker, S. C., Abaan, H. O., Fajardo, K. V. F., & Margulies, E. H. (2011). Accurate

and comprehensive sequencing of personal genomes. Genome research, 21(9), 1498-1505.

This dataset has something wrong with it; one of the sequencing cycles is poor quality.

Report which sequencing cycle has the problem. Remember that a sequencing cycle corresponds to a particular offset in all the reads. For example, if the leftmost read position seems to have a problem consistently across reads, report 0. If the fourth position from the left has the problem, report 3. Do whatever analysis you think is needed to identify the bad cycle. It might help to review the “Analyzing reads by position” video.

`Enter answer here`

### Week 2

#### Quiz 1: Module 2

Q1. Boyer-Moore: How many alignments are skipped by the bad character rule for this alignment?

Note: the number of skips is one less than the number of positions P shifts by. That is, if the pattern shifts by 2 positions, that’s 1 alignment skipped.

Also note: the question is asking only about the alignment shown. Do not consider any other alignments of P to T in your answer.

``T: GGCTATAATGCGTAP: TAATAAA``
`Enter answer here`

Q2. Boyer-Moore: How many alignments are skipped by the good suffix rule in this scenario?

``T: GGCTATAATGCGTAP: TAATTAA``
`Enter answer here`

Q3. Boyer-Moore, true or false: for given P and T, it’s possible that some characters from T will never be examined, i.e., won’t be involved in any character comparisons.

• False
• True

Q4. Consider a version of Boyer-Moore that uses only the bad character rule (no good suffix rule), and say our pattern P is a random string of 50% As and 50% Ts. In which scenario would you expect Boyer-Moore to skip the most alignments?

• The text T consists of 40% As, 40% Ts, 10% Cs and 10%Gs
• The text T consists of 25% As, 25% Ts, 25% Cs and 25%Gs
• The text T consists of 10% As, 10% Ts, 40% Cs and 40%Gs

Q5. The naive exact matching algorithm preprocesses:

• The text T
• Neither
• Both
• The pattern P

Q6. The Boyer-Moore algorithm preprocesses:

• The pattern P
• Neither
• The text T
• Both

Q7. In which of the these scenarios is an offline matching algorithm not appropriate?

• A tool that evaluates a password by comparing it against a large database of bad (easy-to-guess) passwords
• Your web browser’s “find” function that allows you to find a particular word on the web page
• you are currently viewing
• A tool that searches for words in an archive of every speech made in the U.S. Congress

Q8. Say we have a k-mer index containing all 5-mers from T. We query the index using the first 5-mer from P and the index returns a single index hit. What can we say about whether P occurs in T? Assume T is longer than P and that P is at least 6 bases long.

• It definitely does
• It definitely does not
• We don’t know; not enough information

Q9. Say we have a k-mer index containing all k-mers from T and we query it with 3 different k-mers from the pattern P. The first query returns 0 hits, the second returns 1 hit, and the third returns 3 hits. What can we say about whether P occurs in T?

• It definitely does
• It definitely does not
• We don’t know; not enough information

Q10. Which of the following is not an “edit” allowed in edit distance:

• Transposition
• Deletion
• Substitution
• Insertion

#### Quiz 2: Programming Homework 2

Q1. How many alignments does the naive exact matching algorithm try when matching the string \verb|GGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGG|GGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGG (derived from human Alu sequences) to the excerpt of human chromosome 1? (Don’t consider reverse complements.)

`Enter answer here`

Q2. How many character comparisons does the naive exact matching algorithm try when matching the string \verb|GGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGG|GGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGG (derived from human Alu sequences) to the excerpt of human chromosome 1? (Don’t consider reverse complements.)

`Enter answer here`

Q3. How many alignments does Boyer-Moore try when matching the string \verb|GGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGG|GGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGG (derived from human Alu sequences) to the excerpt of human chromosome 1? (Don’t consider reverse complements.)

`Enter answer here`

Q4.Index-assisted approximate matching. In practicals, we built a Python class called \verb|Index|Index

implementing an ordered-list version of the k-mer index. The \verb|Index|Index class is copied below.

class Index(object):
def init(self, t, k):
”’ Create index from all substrings of size ‘length’ ”’
self.k = k # k-mer length (k)
self.index = []
for i in range(len(t) – k + 1): # for each k-mer
self.index.append((t[i:i+k], i)) # add (k-mer, offset) pair
self.index.sort() # alphabetize by k-mer

``def query(self, p):``

We also implemented the pigeonhole principle using Boyer-Moore as our exact matching algorithm.

Implement the pigeonhole principle using \verb|Index|Index to find exact matches for the partitions. Assume P always has length 24, and that we are looking for approximate matches with up to 2 mismatches (substitutions). We will use an 8-mer index.

Download the Python module for building a k-mer index.

Write a function that, given a length-24 pattern P and given an \verb|Index|Index object built on 8-mers, finds all approximate occurrences of P within T with up to 2 mismatches. Insertions and deletions are not allowed. Don’t consider any reverse complements.

How many times does the string \verb|GGCGCGGTGGCTCACGCCTGTAAT|GGCGCGGTGGCTCACGCCTGTAAT, which is derived from a human Alu sequence, occur with up to 2 substitutions in the excerpt of human chromosome 1? (Don’t consider reverse complements here.)

Hint 1: Multiple index hits might direct you to the same match multiple times, but be careful not to count a match more than once.

Hint 2: You can check your work by comparing the output of your new function to that of the \verb|naive_2mm|naive_2mm function implemented in the previous module.

`Enter answer here`

Q5. Using the instructions given in Question 4, how many total index hits are there when searching for occurrences of \verb|GGCGCGGTGGCTCACGCCTGTAAT|GGCGCGGTGGCTCACGCCTGTAAT with up to 2 substitutions in the excerpt of human chromosome 1?

(Don’t consider reverse complements.)

Hint: You should be able to use the \verb|boyer_moore|boyer_moore function (or the slower \verb|naive|naive function) to double-check your answer.

`Enter answer here`

Q6. Let’s examine whether there is a benefit to using an index built using subsequences of T rather than substrings, as we discussed in the “Variations on k-mer indexes” video. We’ll consider subsequences involving every N characters. For example, if we split \verb|ATATAT|ATATAT into two substring partitions, we would get partitions \verb|ATA|ATA (the first half) and \verb|TAT|TAT (second half). But if we split \verb|ATATAT|ATATAT into two subsequences by taking every other character, we would get \verb|AAA|AAA (first, third and fifth characters) and \verb|TTT|TTT (second, fourth and sixth).

Another way to visualize this is using numbers to show how each character of P is allocated to a partition. Splitting a length-6 pattern into two substrings could be represented as \verb|111222|111222, and splitting into two subsequences of every other character could be represented as \verb|121212|121212

The following class \verb|SubseqIndex|SubseqIndex is a more general implementation of \verb|Index|Index that additionally handles subsequences. It only considers subsequences that take every Nth character:

import bisect

class SubseqIndex(object):
“”” Holds a subsequence index for a text T “””

``````def __init__(self, t, k, ival):
""" Create index from all subsequences consisting of k characters
spaced ival positions apart.  E.g., SubseqIndex("ATAT", 2, 2)
extracts ("AA", 0) and ("TT", 1). """
self.k = k  # num characters per subsequence extracted``````

For example, if we do:

ind = SubseqIndex(‘ATATAT’, 3, 2)
print(ind.index)

we see:

[(‘AAA’, 0), (‘TTT’, 1)]

And if we query this index:

p = ‘TTATAT’
print(ind.query(p[0:]))

we see:

12
[]

because the subsequence \verb|TAA|TAA is not in the index. But if we query with the second subsequence:

print(ind.query(p[1:]))

we see:

1
[1]
because the second subsequence \verb|TTT|TTT is in the index.

Write a function that, given a length-24 pattern P and given a \verb|SubseqIndex|SubseqIndex object built with k = 8 and ival = 3, finds all approximate occurrences of P within T with up to 2 mismatches.

When using this function, how many total index hits are there when searching for \verb|GGCGCGGTGGCTCACGCCTGTAAT|GGCGCGGTGGCTCACGCCTGTAAT with up to 2 substitutions in the excerpt of human chromosome 1? (Again, don’t consider reverse complements.)

Hint: See this notebook for a few examples you can use to test your function.

`Enter answer here`

### Week 3

#### Quiz 1: Module 3

Q1. The value in each edit-distance matrix element depends on its neighbors:

• Above, to the left, and to the right
• To the upper-left, to the left and to the lower-left
• To the left and to the lower-left
• Above, to the left, and to the upper-left

Q2. Say we have filled in the approximate matching matrix and identified the minimum value (say, 2) in the bottom row. Now we would like to know the shape of the corresponding 2-edit alignment, i.e. we would like to know where the insertions, deletions and substitutions are. We use a procedure called:

• Filling
• Binary search
• Pathing
• Traceback

Q3. Say the edit distance between DNA strings α and β is 407. What is the edit distance between α and β\verb|G|G (β concatenated with the base \verb|G|G)

• could be any of the other choices
• 406
• 407
• 408

Q4. Say we are using dynamic programming to find approximate occurrences of P in T. About how many dynamic programming matrix elements do we have to fill in?

• |P| |T|
• |P| + |T|
• |T|^2 (squared)
• |P|^2 (squared)

Q5. Local alignment is different from global alignment because:

• It finds similarities between substrings rather than between entire strings
• There is no dynamic programming algorithm for solving it
• It compares three strings instead of two
• Insertions and deletions incur no penalty

Q6. The first law of assembly says that if a prefix of read A is similar to a suffix of read B, then…

• A and B might overlap in the genome
• A and B must be from different genomes
• Read B might have a sequencing error at the end
• A and B should not be joined in the final assembly

Q7. The second law of assembly says that more coverage leads to…

• less accurate results
• more and longer overlaps between reads
• more sequencing errors

Q8. In an overlap graph, the nodes of the graph correspond to

• Bases
• Genomes
• Overlaps

Q9. The overlap graph is a useful structure because:

• It makes it faster to compare reads
• A reconstruction of the genome corresponds to a path through the graph
• It helps to ignore long overlaps

Q10. Which of the following is not a reason why an overlap might contain sequence differences (i.e. might not be an exact match):

• Insufficient coverage
• Polyploidy
• Sequencing error

#### Quiz 2: Programming Homework 3

Q1. What is the edit distance of the best match between pattern GCTGATCGATCGTACG|GCTGATCGATCGTACG and the excerpt of human chromosome 1? (Don’t consider reverse complements.)

`Enter answer here`

Q2. What is the edit distance of the best match between pattern GATTTACCAGATTGAG|GATTTACCAGATTGAG and the excerpt of human chromosome 1? (Don’t consider reverse complements.)

`Enter answer here`

Q3. In a practical, we saw a function for finding the longest exact overlap (suffix/prefix match) between two strings. The function is copied below.

def overlap(a, b, min_length=3):
“”” Return length of longest suffix of ‘a’ matching
a prefix of ‘b’ that is at least ‘min_length’
characters long. If no such overlap exists,
return 0. “””
start = 0 # start all the way at the left
while True:
start = a.find(b[:min_length], start) # look for b’s prefix in a
if start == -1: # no more occurrences to right
return 0

Say we are concerned only with overlaps that (a) are exact matches (no differences allowed), and (b) are at least \verb|k|k bases long. To make an overlap graph, we could call \verb|overlap(a, b, min_length=k)|overlap(a, b, min_length=k) on every possible pair of reads from the dataset. Unfortunately, that will be very slow!

Consider this: Say we are using k=6, and we have a read \verb|a|a whose length-6 suffix is \verb|GTCCTA|GTCCTA. Say \verb|GTCCTA|GTCCTA does not occur in any other read in the dataset. In other words, the 6-mer \verb|GTCCTA|GTCCTA occurs at the end of read \verb|a|a and nowhere else. It follows that \verb|a|a’s suffix cannot possibly overlap the prefix of any other read by 6 or more characters.

Put another way, if we want to find the overlaps involving a suffix of read \verb|a|a and a prefix of some other read, we can ignore any reads that don’t contain the length-k suffix of \verb|a|a. This is good news because it can save us a lot of work!

The most important point is that we do not call \verb|overlap(a, b, min_length=k)|overlap(a, b, min_length=k) if \verb|b|b does not contain the length-k suffix of \verb|a|a.

Download and parse the read sequences from the provided Phi-X FASTQ file. We’ll just use their base sequences, so you can ignore read names and base qualities. Also, no two reads in the FASTQ have the same sequence of bases. This makes things simpler.

Next, find all pairs of reads with an exact suffix/prefix match of length at least 30. Don’t overlap a read with itself; if a read has a suffix/prefix match to itself, ignore that match. Ignore reverse complements.

Hint 1: Your function should not take much more than 15 seconds to run on this 10,000-read dataset, and maybe much less than that. (Our solution takes about 3 seconds.) If your function is much slower, there is a problem somewhere.

Hint 2: Remember not to overlap a read with itself. If you do, your answers will be too high.

Hint 3: You can test your implementation by making up small examples, then checking that (a) your implementation runs quickly, and (b) you get the same answer as if you had simply called \verb|overlap(a, b, min_length=k)|overlap(a, b, min_length=k) on every pair of reads. We also have provided a couple examples you can check against.

Picture the overlap graph corresponding to the overlaps just calculated. How many edges are in the graph? In other words, how many distinct pairs of reads overlap?

`Enter answer here`

Q4. Picture the overlap graph corresponding to the overlaps computed for the previous question. How many nodes in this graph have at least one outgoing edge? (In other words, how many reads have a suffix involved in an overlap?)

`Enter answer here`

### Week 4

#### Quiz 1: Module 4

Q1. The slow (sometimes called “brute force”) algorithm for finding the shortest common superstring of the strings in set S involves:

• Iteratively removing strings from S that don’t belong in the superstring
• Trying all orderings of the strings in S
• Concatenating the strings in of S
• Finding the longest common substring of the strings in S

Q2. Which of the following is not a true statement about the slow (brute force) shortest common superstring algorithm.

• It might collapse repetitive portions of the genome
• The superstring returned might be longer than the shortest possible one
• The amount of time it takes grows with the factorial of the number of input strings

Q3. Which of the following is not a true statement about the greedy shortest common superstring formulation of the assembly problem?

• The amount of time it takes grows with the factorial of the number of input strings
• It might collapse repetitive portions of the genome
• The superstring returned might be longer than the shortest possible one

Q4. True or false: an Eulerian walk is a way of moving through a graph such that each node is visited exactly once

• False
• True

Q5. If the genome is repetitive and we try to use the De Bruijn Graph/Eulerian Path method for assembling it, we might find that:

• There is more than one Eulerian path
• The genome “spelled out” along the Eulerian path is not a superstring of the reads
• The De Bruijn graph breaks into pieces

Q6. In a De Bruijn assembly graph for given k, there is one edge per

• k-mer
• k-1-mer
• genome

Q7. Which of the following does not help with the problem of assembling repetitive genomes:

• Increasing minimum required overlap length for the overlap graph

#### Quiz 2: Programming Homework 4

Q1. In a practical, we saw the \verb|scs|scs function (copied below along with \verb|overlap|overlap) for finding the shortest common superstring of a set of strings.

``````def overlap(a, b, min_length=3):
""" Return length of longest suffix of 'a' matching
a prefix of 'b' that is at least 'min_length'
characters long.  If no such overlap exists,
return 0. """
start = 0  # start all the way at the left
while True:
start = a.find(b[:min_length], start)  # look for b's suffx in a
if start == -1:  # no more occurrences to right
return 0
# found occurrence; check for full suffix/prefix match
if b.startswith(a[start:]):
return len(a)-start
start += 1  # move just past previous match

import itertools

def scs(ss):
""" Returns shortest common superstring of given
strings, which must be the same length """
shortest_sup = None
for ssperm in itertools.permutations(ss):
sup = ssperm[0]  # superstring starts as first string
for i in range(len(ss)-1):
# overlap adjacent strings A and B in the permutation
olen = overlap(ssperm[i], ssperm[i+1], min_length=1)
# add non-overlapping portion of B to superstring
sup += ssperm[i+1][olen:]
if shortest_sup is None or len(sup) < len(shortest_sup):
shortest_sup = sup  # found shorter superstring
return shortest_sup  # return shortest``````

It’s possible for there to be multiple different shortest common superstrings for the same set of input strings. Consider the input strings \verb|ABC|ABC, \verb|BCA|BCA, \verb|CAB|CAB. One shortest common superstring is \verb|ABCAB|ABCAB but another is \verb|BCABC|BCABC and another is \verb|CABCA|CABCA.

What is the length of the shortest common superstring of the following strings?

CCT, CTT, TGC, TGG, GAT, |ATT

`Enter answer here`

Q2. How many different shortest common superstrings are there for the input strings given in the previous question?

Hint 1: You can modify the \verb|scs|scs function to keep track of this.

Hint 2: You can look at these examples to double-check that your modified \verb|scs|scs is working as expected.

`Enter answer here`

Q3. Download this FASTQ file containing synthetic sequencing reads from a mystery virus:

All the reads are the same length (100 bases) and are exact copies of substrings from the forward strand of the virus genome. You don’t have to worry about sequencing errors, ploidy, or reads coming from the reverse strand.

Assemble these reads using one of the approaches discussed, such as greedy shortest common superstring. Since there are many reads, you might consider ways to make the algorithm faster, such as the one discussed in the programming assignment in the previous module.

How many As are there in the full, assembled genome?

Hint: the virus genome you are assembling is exactly 15,894 bases long

`Enter answer here`

Q4. How many Ts are there in the full, assembled genome from the previous question?

`Enter answer here`

#### Get All Course Quiz Answers of Genomic Data Science Specialization

Introduction to Genomic Technologies Coursera Quiz Answers

Python for Genomic Data Science Coursera Quiz Answers

Algorithms for DNA Sequencing Coursera Quiz Answers

Command Line Tools for Genomic Data Science Coursera Quiz Answers

Bioconductor for Genomic Data Science Coursera Quiz Answers

Statistics for Genomic Data Science

##### Team Networking Funda

Welcome to the official Author Page of Team Networking Funda! Here, we are dedicated to unraveling the intricate world of networking, connectivity, and team dynamics. Our mission is to provide you with insightful, actionable advice and solutions that will help you build strong connections, foster collaboration, and achieve success in all aspects of your professional life.

🌐 Networking Insights: Dive into the art of networking with us, as we explore strategies, tips, and real-world examples that can elevate your networking game. Whether you're a seasoned pro or just starting, we have valuable insights to offer.

🤝 Team Synergy: Discover the secrets to creating high-performing teams. We delve into team dynamics, leadership, and communication to help you unlock the full potential of your team and achieve outstanding results.

🚀 Professional Growth: Explore the tools and techniques that can accelerate your professional growth. From career development to personal branding, we're here to guide you toward achieving your goals.

🌟 Success Stories: Be inspired by success stories, case studies, and interviews with experts who have mastered the art of networking and teamwork. Learn from their experiences and apply their insights to your journey.

💬 Engage and Connect: Join the conversation, leave comments, and share your own networking and team-building experiences. Together, we can create a vibrant community of like-minded professionals dedicated to growth and success.

Stay tuned for a wealth of resources that will empower you to excel in your professional life. We're here to provide you with the knowledge and tools you need to thrive in today's interconnected world.

We are Team Networking Funda, a group of passionate authors and networking enthusiasts committed to sharing our expertise and experiences in the world of networking and team building. With backgrounds in [Your Background or Expertise], we bring a diverse range of perspectives and insights to help you navigate the challenges and opportunities of professional networking and teamwork.

error: Content is protected !!