Ask Question, Ask an Expert


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, }, 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

You can use a stack to check if a programming statement or

You can use a Stack to check if a programming statement or a formula has balanced parentheses. Write a Windows application that provides a text box for the user to enter an expression with parenthesis. Provide a Check Pa ...

1 can a host have more than one multicast address explain2

1. Can a host have more than one multicast address? Explain. 2. A multicast router is connected to four networks. The interest of each network is shown below. What is the group list that should be advertised by the route ...

1 what techniques can be used to reduce page table

1. What techniques can be used to reduce page table shadowing induced overhead? 2. What techniques can be used to reduce NPT induced overhead? 3. One of the biggest impediments to widespread use of virtual machines is th ...

Compare the performance of shell sort implementations that

Compare the performance of shell sort implementations that use respectively the sequence of decrements n/2, n/4, n/8, ..., 1 and 2 P -1, ..., 31, 15, 7, 3, 1. Use random data sets and use the number of comparisons and mo ...

In 300 words or more plesae answer the followinginformation

In 300 words or more plesae answer the following: Information technology professionals face many ethical obligations, conflicts, and dilemmas. Discuss ethical issues an IT professional might face. Consider the new trends ...

In an 80211 communication the size of the payload frame

In an 802.11 communication, the size of the payload (frame body) is 1200 bytes. The station decides to fragment the frame into three fragments, each of 400 payload bytes. Answer the following questions: a. What would be ...

Objectivesdesign and plan the implementation of a web

Objectives Design and plan the implementation of a web architecture to support the online presence of a newspaper company. The design must include diagram(s) of the network and web architecture and have installation and ...

Create a php script allows me to remain on irc cloud

Create a PHP script allows me to remain on IRC Cloud without disconnecting. The script should have a $user / $password which we can edit with our username/pw. Then I can run it on a VPS and it will be basically make my I ...

1 choose three software solutions based on self-regulation

1. Choose three software solutions based on self-regulation. Study the solutions and discuss how they work. 2. Study the various forms of activism. Comment on the effectiveness of each. 3. Software rating, although helpf ...

Wvcc has decided to purchase a standalone firewall reread

WVCC has decided to purchase a standalone firewall. Reread the "Improved Performance and Security for the Edge of the Network" section of the chapter to understand WVCC's requirements for the firewall. Do some Internet r ...

  • 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

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