Practice core computational biology skills by representing DNA as strings, finding patterns, computing complements, and comparing sequences with simple algorithms.
Read each problem carefully. Show your work in the space provided. Treat each DNA sequence as a string made from the characters A, C, G, and T.
Using algorithms to search, compare, and analyze DNA sequences
Computer Science - Grade 9-12
- 1
In DNA string analysis, each nucleotide is represented by one character: A, C, G, or T. For the DNA string ACGTACGTA, what is the length of the string, and what character is at index 0 if indexing starts at 0?
- 2
Find all starting positions of the pattern ATG in the DNA string CCATGATGTA. Use 0-based indexing.
- 3
A simple pattern matching algorithm checks every possible starting position in a DNA string. For text length n = 20 and pattern length m = 5, how many starting positions must be checked?
- 4
Compute the complementary DNA strand for the sequence ACGTTA. Use the base-pairing rules A pairs with T and C pairs with G.
- 5
Compute the reverse complement of the DNA sequence AGTC. First find the complement, then reverse the order.
- 6
Count how many times each nucleotide appears in the DNA string AAGCTTACGA. Report the counts for A, C, G, and T.
- 7
The GC content of a DNA string is the percentage of characters that are G or C. Find the GC content of the string GCGTATGC as a percentage.
- 8
A motif is a short DNA pattern that may have biological meaning. In the DNA string TACGATACGA, find all occurrences of the motif ACGA using 0-based indexing.
- 9
Two DNA strings are compared position by position. The Hamming distance is the number of positions where the strings differ. Find the Hamming distance between AACCT and AAGCA.
- 10
A pattern match with up to 1 mismatch is allowed. Does the pattern ACG match the substring ATG with at most 1 mismatch? Explain your answer.
- 11
For the DNA string ATATAT, list all 3-mers in order. A 3-mer is any substring of length 3.
- 12
A frequency table counts how often each k-mer appears. For the string ATATAT and k = 2, make a frequency table for all 2-mers that appear.
- 13
The naive exact matching algorithm compares a pattern to the text at each possible starting position until it finds a match or mismatch. In the worst case, what is the time complexity in terms of text length n and pattern length m?
- 14
A DNA sequence is read by a sequencing machine as short fragments called reads. Suppose the reads are ATGC, TGCA, and GCAT. If each read overlaps the next by 3 characters, what assembled sequence do they form?
- 15
Write clear pseudocode for a function countPattern(text, pattern) that returns the number of exact occurrences of pattern in text. The function should allow overlapping matches.