Redundant sequence identi cation

Assignment Help Theory of Computation
Reference no: EM13728


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


A non-empty string is called a minimal unique substring of s if and only if it satis es.

(i) occurs exactly once in s (uniqueness),
(ii) all proper pre xes 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.


Redundant sequence identi cation. 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.


Let S = {s1, s2, . . . , sk} denote a set of k genomes. The problem of ngerprinting 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 ngerprint of si.

Give an algorithm to enumerate a ngerprint for each input genome, if one exists. Assume that no two input genomes are identical.

A string s is said to be periodic with a period α , if s is αk for some k ≥2. 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.


A non-empty string is called a repeat pre x of a string s if is a pre x of s. Give a linear time algorithm to nd the longest repeat pre x of s.


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 justi cation of why you think your algorithm is correct | meaning, how it guarantees nding the minimial cover.

Reference no: EM13728

Previous Q& A

  Venture capital and private equity

Venture Capital & Private Equity It is argued that VC and PE houses achieve superior returns through ruthlessly focussing management on short to medium term outcomes.

  Antisymmetric relations

How many relations on A are both symmetric and antisymmetric?

  Write a paper on organizational behavior class

Write a paper on Organizational Behavior Class


What does the term entrepreneurship mean to you?

  State exercises criminal jurisdiction

Discuss to what extent a state exercises criminal jurisdiction over individuals.

  Cloud computing assignment

WSDL service that receives a request for a stock market quote and returns the quote

  Analyzing the blink alive code

Analyzing the Blink Alive code - Embedded Systems Design

  Write a vhdl code for soda vending machine

Write a VHDL code that implements the above soda machine. You have to turn in the following: A state diagram showing the implementation of your design. Clearly show all the states and the conditions on which transitions occur.

  Suggest a swot analysis for the company

Considering the micro and macro levels of marketing, please suggest a SWOT analysis for the company NutriSystem

  London congestion charge

Generate revenue for city are under consideration. The two proposals are London Congestion Charge and Charging for Firefighting.


Write a Review


Similar Q& A

  Finite-state machine design

Create a finite-state machine design to turn your FPGA development board into a simple programmable music box.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd