Computer Science: Computational Biology: DNA Strings and Pattern Matching
Using algorithms to search, compare, and analyze DNA sequences
Computer Science: Computational Biology: DNA Strings and Pattern Matching
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?
Count every character in the string, including repeated letters.
The length of the string is 9. The character at index 0 is A because index 0 refers to the first character. - 2
Find all starting positions of the pattern ATG in the DNA string CCATGATGTA. Use 0-based indexing.
The pattern ATG starts at positions 2 and 5. At index 2 the substring is ATG, and at index 5 the substring is also ATG. - 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?
The last possible match begins when there are exactly m characters left.
The algorithm must check 16 starting positions. This is calculated by n - m + 1, so 20 - 5 + 1 = 16. - 4
Compute the complementary DNA strand for the sequence ACGTTA. Use the base-pairing rules A pairs with T and C pairs with G.
The complementary strand is TGCAAT. Each A changes to T, each T changes to A, each C changes to G, and each G changes to C. - 5
Compute the reverse complement of the DNA sequence AGTC. First find the complement, then reverse the order.
Reverse complement is not the same as only taking the complement.
The complement of AGTC is TCAG. Reversing TCAG gives GACT, so the reverse complement is GACT. - 6
Count how many times each nucleotide appears in the DNA string AAGCTTACGA. Report the counts for A, C, G, and T.
The counts are A = 4, C = 2, G = 2, and T = 2. Counting each character in AAGCTTACGA gives four A characters and two of each other nucleotide. - 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.
Count only G and C characters for the numerator.
The GC content is 62.5 percent. There are 5 G or C characters out of 8 total characters, and 5 divided by 8 equals 0.625. - 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.
The motif ACGA occurs at positions 1 and 6. The substring from index 1 to index 4 is ACGA, and the substring from index 6 to index 9 is ACGA. - 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.
Compare only characters in the same position.
The Hamming distance is 2. The strings differ at position 2, where C and G are different, and at position 4, where T and A are different. - 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.
Yes, ACG matches ATG with at most 1 mismatch. The first and third characters match, and only the middle characters C and T are different. - 11
For the DNA string ATATAT, list all 3-mers in order. A 3-mer is any substring of length 3.
Slide a window of length 3 one character at a time.
The 3-mers are ATA, TAT, ATA, and TAT. They start at positions 0, 1, 2, and 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.
The 2-mers are AT, TA, AT, TA, and AT. The frequency table is AT = 3 and TA = 2. - 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?
Think about the number of alignments multiplied by the comparisons per alignment.
The worst-case time complexity is O(nm). There are about n possible starting positions, and up to m characters may be compared at each position. - 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?
The assembled sequence is ATGCAT. ATGC overlaps TGCA by TGC, and TGCA overlaps GCAT by GCA, so the combined sequence is ATGCAT. - 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.
Do not skip ahead by the length of the pattern after a match.
A correct solution loops through each starting position from 0 to length(text) - length(pattern), compares the substring of text with pattern, and increases a count when they are equal. It returns the final count, and overlapping matches are included because the loop moves forward by one position each time.