-
What does the problem set P consist of?
The set P is the set of all decision problems that can be solved by polynomial-time algorithms
all problems with poly-time solutions (sorting, etc)
-
What does the problem set NP consist of?
Problems that can be checked in polynomial time
-
Illustrate how we think the relationship between P and NP works:
We know that P is a subset of NP
We don’t know if it is a proper subset
-
How could we prove P ≠ NP?
we would have to find a single problem in NP that was not in P
-
What does the set NP-complete help us prove?
This set will help us in attempting to prove or disprove that P = NP
-
Examples of the 21 problems Karp came up with as part of the NP-complete set?
- Directed/undirected Hamiltonian circuit
- Knapsack problem
- vertex cover
- steiner cover
- Hitting tree
- Max cut
-
Describe a reduction algorithm for the following scenario:
Suppose we want to solve decision problem A, and we have an algorithm that solves decision problem B
Suppose we can write an algorithm that creates an instance y of problem B for every instance x of problem A s.t.
The algorithm for B answers yes for y iff the answer to problem A is yes for x
Such an algorithm is called a reduction algorithm
-
When can we say that A is poly-time reducible to B (or A is reducible to B)?
(A is proportional to B)
If there exists a poly-time algorithm from decision problem A to decision problem B, then we say A is poly-time reducible to B (or A reduces to B)
Further, if B is in P and A is proportional to B, then A is also in P
-
What sort of ends do the following restriction enzymes produce?
-
In what organism were restriction enzymes first discovered?
E.coli
-
Gel electrophoresis of DNA sample following digestion with EcoRI
-
What is the use of restriction mapping?
Restriction maps are a cheap alternative to sequencing for unknown sequences
-
What is an application of restriction mapping?
- Overlap detection
-
What is an NP complete problem
NP-complete problem, any of a class of computational problems for which no efficient solution algorithm has been found.
There exists no poly-time algorithm to solve it
-
What is the classification of the Double Digest problem?
DDP is NP-complete
-
- If and only if there is a solution for this DDP, then there is a solution for the original SPP (set partitioning problem). This means SPP can be reduced in poly-time to DDP and DDP is NP-complete
-
Describe what happens during a partial digest:
- DNA is exposed to a restriction enzyme for only a limited amount of time to prevent it from being cut at all restriction sites
- All possible restriction fragments between every two (not necessarily consecutive) cuts are generated
- The resulting set of fragment sizes is used to determine the positions of the restriction sites in the DNA sequence
-
Partial Digest fundamentals:
X=
n=
DX=
-
Formulation of the Partial Digest Problem
-
Define: Brute force Algorithm
Also known as exhaustive search algorithms; examine every possible variant to find a solution
Efficient in rare cases; usually impractical
-
Partial Digest Brute Force algorithm
-
What is the efficiency of BruteForcePDP? How might we improve it?
BruteForcePDP takes time since it must examine all possible sets of positions.
One way to improve the algorithm is to limit the values of x i to only those values which occur in L.
-
How did Skinea's Algorithm try to solve the PDP?
Given PDP data, focus on the largest fragment
-
How does Skinea's algorithm perform?
-
What is a megavirus?
- Special case of Mimi virus
- It is a very big virus with a small genome
-
When to use recursion vs iteration?
If time complexity is the point of focus, and the number of recursive calls would be large, it is better to use iteration. However, if time complexity is not an issue and shortness of code is, recursion would be the way to go.
-
How do you test runtime of your function?
- the benchmark function!
- @benchmark test_function()
-
Turnip vs Cabbage gene order comparison
-
-
-
Name and define four different genome rearrangement operations
example sequence: 12345
Reversal: 12345 -> 12435
Translocation: 123 & 456 -> 126 & 453
Fusion: 12 & 345 -> 12345
Fission: 12345 -> 12 & 345
-
genome rearrangement:
-
genome rearrangement:
-
genome rearrangement:
-
genome rearrangement:
-
What is a synteny block?
block of color describing gene similarity on a genome map
-
Diseases associated with genome rearrangement (3):
- Robertsonian Translocation (translocation between 13 and 14, often pregnancy loss or fetal abnormality)
- Philadelphia Chromosome (translocation between chromosome 9 and 22, often myelogenous leukemia)
- Colon cancer
-
Reversal Distance Problem:
Goal=?
Input=?
output=?
-
How do we measure performance of an algorithm?
Time, space
-
Greedy reversal sort algorithm:
-
What is the purpose of an approximation algorithm
These algorithms find approximate solutions rather than optimal solutions
-
Approximation ratio of algorithm A on the input is:
-
For the approximation ratio, if you were trying to minimize the problem, which part of the ratio would be larger?
- A( )
- Minimization is larger than the optimum
-
What is APX?
- APX is the set of NP problems that have a P-time approximation algorithm with constant approximation ratio
- "My solution is not optimal, but it is not worse than 1.1 (10%) off of optimal"
-
For algorithm A that minimizes objective function (minimization algorithm):
-
BreakPointReversal search attempts to (eliminate _#_ of breakpoints every _#_ steps) and will not use more than _#_ the minimum number of reversals)
At least one breakpoints every two steps, and no more than four times the minimum number of reversals
-
Evaluate performance guarantee of the BreakpointReversalSort algorithm
hint:
Performance guarantee:
-
In the DCJ model, how is the genome grouped?
into chromosomes, linear/circular
-
(2,3,-4)
-
-
|
|
