matlab
ALGORITHMS IN BIOINFOMATICS (MATLAB )
1. Given L=[1,3,4,4,5,7,9,11,14], make a quick conclusion that a PDP answer can never be
found. DO NOT apply skiena's algorithm.
2. Given L = [1,1,1,2,2,3,3,3,4,4,5,5,6,6,6,9,9,10,11,12,15], 1. Provide detailed discussion and
exact calculation of search space (expression only, no actual number) when a naive
ute
force is proposed, i.e. try every possible value between 1 to XXXXXXXXXXProvide same analysis
when a 'smart'
ute force is proposed, i.e. only try valid values.
3. Looking the Longest Common Substring Problem: Given two strings X and Y, find the
length of the longest common substring. For example X="abcd" Y="
c", answer is "bc".
1) Propose a 'fast derived' algorithm. Find the size of the search space. Provide Big O. 2)
Propose an improved version of (1) Provide Big O.
4. Given L={1,1,4,5,6,8,9,10,11,12} in PDP, why 3 can not be part of the answer?
5. For a complete search tree for 3-mers in the 3-letter alphabet {a, b, c}. What is the total
number of leaves? What is the total number of nodes? How to represent the root?
6. Shortest Binary Superstring Problem: Given a set of strings of binary 0 or 1, find a shortest
string that contains all of them. Description Input: Strings s_1, s_2, ..., s_n. Output: A string
s that contains all strings s_1, s_2,..., s_n as substrings, such that the length of s is
minimized. Example: Strings {000,001,010,011,100,101,110,111}. s= XXXXXXXXXXOutline a
very detailed naive
ute forth solution for the problem. Use the following string set up
{00000,010,0001,0111}, i.e 4 strings of length {5,3,4,4} Provide your search space and
show exact the number of testing cases (in expression). Try to propose a more efficient
ute forth solution and justify it but no analysis
7. Let DNA (5 x 40) be CCTGATAGACGCTATCTGGCTATCCACGTACGTAGGTCCT
A G T A C T G G T G T A C A T T T G A T A C G T A C G T A C A C C G G C A A C C
A A A C G T A C G T G C A C C C T C T T T C T T C G T G G C T C T G G C C A A C
A G C C T C C G A T G T A A G T C A T A G C T G T A A C T A T T A C C T G C C A
CTGTTATACAACGCGTCATGGCGGGGTATGCGTTTTGGTC Let l=3 and s=(5,4,3,2,1) what
is the profile for the l-mer the the score(s) the consensus string What is a possible median
string? Let v=GGGG, what is the totalDistance(v, DNA) what is the score and what is s?
8. The eight queens puzzle is the problem of placing eight chess queens on an 8x8
chessboard so that no two queens attack each other. Thus, a solution requires that no two
queens share the same row, column, or diagonal. The eight queens puzzle is an example of
the more general n-queens problem of placing n queens on an n x n chessboard, where
solutions exist for all natural numbers n >= 4. Outline a detailed naive
ute forth solution
for the 4-queens problem. Provide your search space and show exact the number of
testing cases (in decimal expression). Apply the same strategy, what is the number of
testing cases for 8-queens problem? Could you do better? Try to propose a more efficient
solution and justify it.