Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Computer Engineering Expert

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

1nbspa methodology describes how things should be done

1:  A methodology describes how things should be done , design a table showing how you can map the main activities of " Hospital  Management Project  "into the knowledge areas ? Q 2: Using Microsoft Project 2007/2010 too ...

1 find the greatest common divisor of 234 and 1242 find r

1. Find the greatest common divisor of 234 and 124. 2: Find r and s such that 8,092r + 1,111s = 1. 3: Find a counterexample to the claim that if the greatest common divisor of a and b is not 1, there exists a unique r an ...

Think about a time when you were required to accomplish a

Think about a time when you were required to accomplish a new or nonroutine task at work that had the potential to cause injury or illness. Discuss how a management of change process could be used to reduce the risks. Wh ...

1 design and implement a function to find all negative

1. Design and implement a function to find all negative values within a given list. Your function should return a new list containing the negative values. When does the worst case occur and what is the run time for that ...

Discussionthe benefits of microsoft officebullidentify at

Discussion "The Benefits of Microsoft Office" • Identify at least two ways that a user can combine content from two or more Office applications. Explain the major benefits of doing so for each identified example. • Descr ...

1 what is the relationship between a base station and a

1. What is the relationship between a base station and a mobile switching center? 2. What are the functions of a mobile switching center? 3. Which is better, a low reuse factor or a high reuse factor? Explain your answer ...

In sect 1013 we state that sender or message authentication

In Sect. 10.1.3 we state that sender (or message) authentication always implies data integrity. Why? Is the opposite true too, i.e., does data integrity imply sender authentication? Justify both answers. In this exercise ...

Suppose a new class of users the system security officers

Suppose a new class of users, the system security officers (SSOs), were to be added to the access control matrix discussed in Section 26.2.2. Augment the matrix with the change right. This right allows the user to alter ...

1 what is the best page size if entries now become 128

1. What is the best page size if entries now become 128 bytes? 2. Based on 5.10.1, what is the best page size if pages are half full? 3. Based on 5.10.2, what is the best page size if using a modern disk with a 3 ms late ...

1 draw a plan of how you will go about setting up a

1. Draw a plan of how you will go about setting up a Disaster Recovery Committee, indicating who will be in it and why. Also send a memo to the committee members telling them about the first organizing meeting, and list ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

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.

Ask Now Help with Problems, Get a Best Answer

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

Describe what you learned about the impact of economic

Describe what you learned about the impact of economic, social, and demographic trends affecting the US labor environmen