Restriction maps

The Double Digest Problem (DDP)

Task 1

• In R, create a function DoubleDigestProblem() for the brute-force DDP algorithm for one possible arrangement of fragments.

• Input:

  • A multiset of fragments generated by digestion by enzyme A.
  • A multiset of fragments generated by digestion by enzyme B.
  • A multiset of fragments generated by digestion by enzymes A + B.

• Output:

  • Positions of restriction sites for enzyme A.
  • Positions of restriction sites for enzyme B.

• Modify it to search through all possible arrangements of fragments.

The Partial Digest Problem (PDP)

Task 2

• In R, implement a function Place() according to the following pseudocode.

• Input:

  • deltaX A multiset of fragments lengths.
  • X A list of the current positions of the restriction sites.
  • width Length of the DNA molecule i.e. the size of the longest fragment.

• Output:

  • A list of the positions of the restriction sites.

• Δ(y, X) is a multiset of lengths between value y and all values in X.

• Hint: Create additional function Remove(), which removes from deltaX all used lengths Δ(y, X).

Place(deltaX, X, width)
1   if deltaX is empty
2     output X
3     return
4   y ← the maximum element from deltaX
5   if Δ(y, X) ⊆ deltaX
6     add y to X and remove the lengths Δ(y, X) from deltaX
7     Place(deltaX, X, width)
8     remove y from X and add the lengths Δ(y, X) to deltaX
9   if Δ(width - y, X) ⊆ deltaX
10    add width - y to X and remove the lengths Δ(width - y, X) from deltaX
11    Place(deltaX, X, width)
12    remove width - y from X and add the lengths Δ(width - y, X) to deltaX
13  return

Task 3

• In R, implement a function PartialDigestProblem() according to the following pseudocode.

• Input:

  • deltaX A multiset of fragments lengths.

PartialDigestProblem(deltaX)
1   width ← the maximum element from deltaX
2   delete the maximum element from deltaX
3   X ← {0, width}
4   Place(deltaX, X, width)

Download files from GitHub

Basic Git settings

• Configure the Git editor

  git config --global core.editor notepad

• Configure your name and email address

  git config --global user.name "Zuzana Nova"
  git config --global user.email z.nova@vut.cz

• Check current settings

  git config --global --list

• Create a fork on your GitHub account. On the GitHub page of this repository find a Fork button in the upper right corner.

• Clone forked repository from your GitHub page to your computer:

git clone <fork repository address>

• In a local repository, set new remote for a project repository:

git remote add upstream https://github.com/mpa-prg/exercise_06.git

Send files to GitHub

Create a new commit and send new changes to your remote repository.

• Add file to a new commit.

git add <file_name>

• Create a new commit, enter commit message, save the file and close it.

git commit

• Send a new commit to your GitHub repository.

git push origin main