\n",
"\n",
"**Homework Information:** Some of the problems are probably too long to be done the night before the due date, so plan accordingly. Late problem sets will be penalized by a factor of\t70.71% for each class meeting after the due date. Feel free to get help from others, but the work you submit in should be your own."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false,
"section": "signature"
},
"outputs": [],
"source": [
"# Replace the following string values with the requested information\n",
"class Student:\n",
" first = \"Your given name\"\n",
" last = \"Your family name\"\n",
" onyen = \"Your UNC Onyen\"\n",
" pid = \"Your UNC pid\""
]
},
{
"cell_type": "markdown",
"metadata": {
"number": 1,
"section": "problem"
},
"source": [
"---\n",
"**Problem #1:** Find the longest common subsequence (LCS) between the first 100 bases and the last 100 bases of the [*Salmonella Typhimurium*](http://csbio.unc.edu/mcmillan/Comp555S18/data/SalmonellaTyphimurium.fa) genome. Report both the length of the LCS as well as the subsequence. Do not include the *+* sign at the start of the genome."
]
},
{
"cell_type": "raw",
"metadata": {
"number": 1,
"section": "answer"
},
"source": [
"Enter your answer here."
]
},
{
"cell_type": "markdown",
"metadata": {
"number": 2,
"section": "problem"
},
"source": [
"---\n",
"**Problem #2:** Find the length of the longest *embedded* common subsequence in the following: \n",
"\n",
" \"GTACAAAAACAACACAAGAAAAGACAATAAAATTCCATTCGATTCTATTCAATTGGTACA\"\n",
"\n",
"The longest embedded common subsequence is the longest common subsequence within in a sequence for which no symbol matches itself. As an example, consider \"TAGACATAAG\". The longest common subsequence is the sequence itself, \"TAGACTAAG\", but the longest *embedded* common subsequence is \"TAG\". "
]
},
{
"cell_type": "raw",
"metadata": {
"number": 2,
"section": "answer"
},
"source": [
"Enter your answer here."
]
},
{
"cell_type": "markdown",
"metadata": {
"number": 3,
"section": "problem"
},
"source": [
"---\n",
"**Problem #3:** On your midterm you were asked to find all 16-peptide chains whose molecular weight equals a given target (1024) using the following list of residues ordered by their weights. Most of the algorithms proposed were time-consuming with many possible answers.\n",
"\n",
"```python\n",
"Residues = [\n",
" (186, 'W'), (163, 'Y'), (156, 'R'), (147, 'F'), (137, 'H'), \n",
" (131, 'M'), (129, 'E'), (128, '[K/Q]'), (115, 'D'), (114, 'N'),\n",
" (113, '[I/L]'), (103, 'C'), (101, 'T'), (99, 'V'), (97, 'P'), \n",
" (87, 'S'), (71, 'A'), (57, 'G')\n",
"]\n",
"```\n",
"\n",
"Now consider a slightly different problem: find the *length* of the *shortest peptide chain* whose molecular weight matches a target. This problem can be solved effciently using *dynamic programming*. In order to see how, consider an analogy between finding the shortest peptide combination of a given weight, and the problem of making *exact change* from an arbitrary set of coinage. \n",
"\n",
"In the space below give a reccurance relation for the dynamic program for finding the shortest combination of peptides, *DPShortestPeptideLength(target, Residues)*."
]
},
{
"cell_type": "raw",
"metadata": {
"number": 3,
"section": "answer"
},
"source": [
"Enter your answer here."
]
},
{
"cell_type": "markdown",
"metadata": {
"number": 4,
"section": "problem"
},
"source": [
"---\n",
"**Problem #4:** It is inefficient to create and fully populate a table for *DPShortestPeptideLength(target, Residues)* where every molecular weight less than your given target, as you would for computing exact change. Suggest a more efficient means for representing and populating the memoization of intermediate results needed for *DPShortestPeptideLength(target, Residues)*."
]
},
{
"cell_type": "raw",
"metadata": {
"number": 4,
"section": "answer"
},
"source": [
"Enter your answer here."
]
},
{
"cell_type": "markdown",
"metadata": {
"number": 5,
"section": "problem"
},
"source": [
"**Problem #5: Programming Problem**\n",
"\n",
"Implement a *dynamic programming* solution for *DPShortestPeptideCombination(target, Residues)*, which is similar to the task described in Problem #4, except finds a shortest peptide chain whose molecular weight matches a target. In the space provided below write your function and test it by generating a shortest peptide combination whose molecular weight is 555, 1024, and 2048."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false,
"number": 5,
"section": "answer"
},
"outputs": [],
"source": [
"# Enter your answer here"
]
},
{
"cell_type": "markdown",
"metadata": {
"section": "submit"
},
"source": [
"Click [here to submit](http://csbio.unc.edu/mcmillan/index.py?run=PS.upload) your completed problem set"
]
}
],
"metadata": {
"anaconda-cloud": {},
"celltoolbar": "Edit Metadata",
"kernelspec": {
"display_name": "Python [default]",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.11"
}
},
"nbformat": 4,
"nbformat_minor": 0
}