+1-415-315-9853

info@mywordsolution.com

Engineering

 Civil Engineering Chemical Engineering Electrical & Electronics Mechanical Engineering Computer Engineering Engineering Mathematics MATLAB Other Engineering Digital Electronics Biochemical & Biotechnology

1. Using suffix trees, give an algorithm to find a longest common substring shared among three input strings: s1 of length n1, s2 of length n2 and s3 of length n3.

2. A non-empty string α is called a minimal unique substring of s if and only if it satisfies:

(i) α occurs exactly once in s (uniqueness),

(ii) all proper prefixes of α occur at least twice in s (mimimality), and

(iii) α >= l for some constant l.Give an optimal algorithm to enumerate all minimal unique substrings of s.

3. Redundant sequence identification: Given a set of k DNA sequences, S = {s1, s2........sk }, give an optimal algorithm to identify all sequences that are completely contained in (i.e., substrings of) at least one other sequence in S.

4. Let S = {s1, s2,......,sk} denote a set of k genomes. The problem of  fingerprinting is the task of identifying a shortest possible substring αi from each string si such  that αi is unique to si  i.e., no other genome in the set S has αi. Such an αi will be called a fingerprint of si. (Note that it is OK for αi to be present more than once within si.) Give an algorithm to enumerate a fingerprint for each input genome, if one exists. Assume that no two input genomes are identical.

5. A string s is said to be periodic with a period α , if s is αk for some k>=2. (Note that αk is the string formed by concatenating α k times.) A DNA sequence s is called a tandem repeat if it is periodic. Given a DNA sequence s, determine if it is periodic, and if so, the values for α and k. Note that there could be more than one period for a periodic string. In such a case, you need to report the shortest period.

6. A non-empty string β is called a repeat prefix of a string s if ββ is a prefix of s. Give a linear time algorithm to find the longest repeat prefix of s.

7. Given strings s1 and s2 of lengths m and n respectively, a minimum cover of s1 by s2 is a decomposition s1 = w1w2......wk, where each wi is a non-empty substring of s2 and k is minimized. Eg., given s1 = accgtatct and s2 = cgtactcatc, there are several covers of s1 by s2 possible, two of which are: (i) cover1: s1 = w1w2w3w4 (where w1 = ac, w2 = cgt, w3 = atc, w4 = t) , and (ii) cover2: s1 = w1w2w3w4w5 (where w1 = ac, w2 = c, w3 = gt, w4 = atc, w5 = t). However, only cover1 is a minimal cover. Give an algorithm to compute a minimum cover (if one exists) in O(m + n) time and space. If a minimum cover does not exist your algorithm should state so and terminate within the same time and space bounds. Give a brief justification of why you think your algorithm is correct | meaning, how it guarantees finding the minimial cover (if one exists).

Computer Engineering, Engineering

• Category:- Computer Engineering
• Reference No.:- M91531

Have any Question?

Related Questions in Computer Engineering

Now calculate the relative performance of adders assume

Now calculate the relative performance of adders. Assume that hardware corresponding to any equation containing only OR or AND terms, such as the equations for pi and gi on page B-40, takes one time unit T. Equations tha ...

The autocorrelation array of a 4 x 1 zero mean vector u is

The autocorrelation array of a 4 x 1 zero mean vector u is given by a. What is the KL transform of u? b. Compare the basis vectors of the KL transform with the basis vectors of the 4 x 4 unitary DFf, OCT, DST, Hadamard, ...

Suppose that 95 of the execution time in a certain program

Suppose that 95% of the execution time in a certain program is due to code that can be split into N independent parts each of which can be executed by a separate processor. The remaining 5% is sequential and must execute ...

1 explain why an mospf router can create the shortest path

1. Explain why an MOSPF router can create the shortest path with the source as the root in one step, but DVMRP needs three steps to do so. 2. Explain why PIM is called Protocol Independent Multicast. 3. Which version of ...

1 discuss two lan technologies that are not ethernet or

1. Discuss two LAN technologies that are NOT Ethernet or token ring. 2. Why is Ethernet technology more appealing to users than the rest of the LAN technologies? 3. What do you think are the weak points of TCP/IP? 4. Dis ...

Question 11 corporate culture has been said to be the

Question 1: 1. Corporate culture has been said to be the toughest component of a business to change. Do you agree or disagree with this statement and why? 2. Define the five types of power according to French and Raven's ...

1 indicate dependences and their type2 assume there is no

1. Indicate dependences and their type. 2. Assume there is no forwarding in this pipelined processor. Indicate hazards and add nop instructions to eliminate them. 3. Assume there is full forwarding. Indicate hazards and ...

Write methodsthat compute the area and the perimeter of the

Write methods that compute the area and the perimeter of the ellipse e. Add these methods to a class Geometry. The challenging part of this assignment is to find and implement an accurate formula for the perimeter. Why d ...

1 describe a recursive algorithm for finding the maximum

1. Describe a recursive algorithm for finding the maximum element in an array A of n elements. What is the running time of your algorithm? 2. Draw the recursion trace for the execution of reverseArray(data, 0, 4), on the ...

Consider our implementation of the stack adt using the

Consider our implementation of the Stack ADT using the Python list, and suppose we had used the front of the list as the top of the stack and the end of the list as the base. What impact, if any, would this have on the r ...

• 13,132 Experts

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro