A nucleic acid sequence in a DNA sequence consists of a sequence of 4 possible l

Question

A nucleic acid sequence in a DNA sequence consists of a sequence of 4 possible letter: A C G T. This sequence is represented using the so called Trie data structure. In this case, it is a Quaternary tree in which each letter of a sequence is used as the key. Thus an 'A' in the sequence will create a branch to the leftmost-left, a ‘C, a branch to the middle-left, a ‘G' to the middle right and a 'T' to the rightmost-right. Here is an illustration of such a tree containing nine sequences (A, T. CC, CAA, CCC, GCG CCAA CCG CCAAT CAA CCG CCAA CCAAT The branches are always created in the order ACGT (null children references are not shown) The grey nodes are nodes that contain no sequence (a) Knowing that the longest sequence has a length of N, show that the search for a sequence in this tree will be O(N) b) Knowing that the longest sequence has a length of N, give the maximum number of nodes that such a tree can have. c) Knowing that the longest sequence has a length of N, give the minimum number of nodes that such a tree can have d) Print the non-empty nodes in this tree using post-order traversal

Explanation / Answer

Answer:-

a) The search will start at the root node and will navigate each level grounded on the sequence element. Since the extensive sequence length is N it will have to navigate a depth of N for the search and this will be bounded by O (N).

b) The maximum number of nodes equals to a full quaternary tree which is

               1+4+ 4^2 + 4^3 +...+ 4^h = 1(4^h+1 -1)/(4-1) = 1/3*(4^(h+1)-1)

          Where h is the height of the tree.

c) Minimum number of nodes will be N, 1 at each level.

d) A, CAA, CCAAA, CCAAT, CCAA, CCC, CCG, CC, T

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.