Question: Suffix tree, suffix array and BWT: A). Show the suffix tree for string actgctcggct. B). Compute the suffix array for the same string. C). Compute

Suffix tree, suffix array and BWT:

A). Show the suffix tree for string actgctcggct.

B). Compute the suffix array for the same string.

C). Compute the BWT transformation for the same string.

D). Assume that an implementation of suffix tree for DNA sequences uses 20 bytes per base. Estimate the memory requirement for a suffix tree representation of the human genome, which has 3 billion bases.

E). Estimate the memory requirement for a suffix array representation of the human genome.

F). Estimate the memory requirement for a BWT representation of the human genome.

G). Considering that we are indexing a large database of strings with 3 billions characters, where each character is an integer in the range of 1 to 216. Does this change the memory requirement of suffix array and BWT? What impact it might have on suffix trees?

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock

Sure lets tackle each part systematically A Building the Suffix Tree for the String actgctcggct A suffix tree for a given string is a compressed trie of all the suffixes of the string Heres how you ca... View full answer

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

You have to read the questions from A-G but I have completed A-C already. I have A-C complete. I just need D-G completed. Thank you. Problem 4 (30 points): Suffix tree, suffix array and BWT A). Show...

1. Let S be a set of n keys being mapped to a hash table (also) of size n. Find the expected number of empty slots under uniform hashing assumption. 2. Let S be a set of n keys being mapped to a has...

(6) Let T = lallilla$. (a) Give the suffix tree of T including suffix links. (b) Give the suffix array of T together with the LCP array (we mean the version of the LCP that is used for binary...

a) Compute the Burrows-Wheeler transform of abracadabra b) Represent the BWT you computed in a) via the wavelet tree data structure. Describe why and how it is important to use wavelet tree for BWT...

--------------------------------------------------------------------------- StdDraw: import java.awt.*; import java.awt.event.*; import java.awt.geom.*; import java.awt.image.*; import java.io.*;...

Draw a suffix tree and show the suffix array and LCP array for the following input strings: a. ABCABCABC b. MISSISSIPPI

a ) Draw the suffix tree corresponding to the text T = omrosodomro. In particular, the children of a node should be ordered alphabetically. b ) Provide an example of a string of length n over...

Development plan 1. As usual, create a directory to hold the files for this assignment. 2. Create files trace.cpp and trace.h . You can use a global variable to indicate the trace level, which can be...

JAVA: Help with Binary Search Tree Program ************************ IntBTNode.java ********************************** // File: IntBTNode.java from the package edu.colorado.nodes // Complete...

// File: IntBTNode.java from the package edu.colorado.nodes // Complete documentation is available from the IntBTNode link in: // http://www.cs.colorado.edu/~main/docs //package edu.colorado.nodes;...

Give description on the Linux package management systems, including their respective distros. 1) Introduction about package management system. 2) Description for each of the FIVE package management...

(10 points): Solve the following equation by the method of variation of parameters 2r" + 2x = sect. No credit by any other method.

Edna had an accideni while ompeting in a rodeo. She sustained ficial injuries that required cosmetic surgery. While having the surgery done to restore her appearance, she had additional surgery done...

Questions Q1. Write a Python program to retrieve the first and last colors from the following list: color_list = ["red", "green", "white", "blue", "black") Q2. Given the following dictionary,...