General information for programming exercises

• Each group gets access to a svn directory at https://svn.mi.fu-berlin.de/agbio/advancedAlgo/SS12/GroupX (Groups at ProgrammingGroupList)
• The solution to each exercise has to be checked in as a file named exerciseY.cpp (case sensitive, no subdirectories!) before the respective deadline.
• The program must compile on a Linux Pool machine (https://wiki.mi.fu-berlin.de/w/IT/ServicesStudentPools) with g++ -pedantic -Wall -ansi -O3 -o exerciseY exerciseY.cpp
• The final version of your application note also have to be checked in as PDF file exerciseY_Note.pdf

Exercise 1

Read mapping with semi global alignment

Deadline: 02.05.2012 9:00 a.m.

• Write a C++ program that:
  • reads two fast files genome.fa and reads.fa where genome.fa contains a single sequence and reads.fa contains an unknown number of reads.
  • uses semi global alignment with dynamic programming for each read to find all matching positions with edit distance at most k.
  • implements the semi global alignment with and without the Ukkonen trick.
  • creates a file containing for each read all hits (startPos, endPos, errors).

• Test your program on the given Dataset (will be added)
• Compare the performance of the naive approach and the Ukkonen trick. Also use the RazerS read mapper in Seqan and compare the runtimes.
• Write a short application note (no more than 1-2 pages) where you describe your implementation and your observations.

Format specifications

The program usage should be: ./exercise1 <genome.fasta> <reads.fasta> <k> <m> where k its the number of allowed errors and m is either 0 (without Ukkonen) or 1 (with Ukkonen)

The program should produce an output file named hits.result with one line for each hit in the format:

<read_id>, <start_pos>, <end_pos>, <errors>

Point scheme

For each exercise you can score 4 Points, 3 for the program and 1 for the application note. For the program:
3 Pts = program runs without errors
2 Pts = program contains small errors
1 Pts = program contains critical errors
0 Pts = no program submitted

Requirements: You have to reach at least 75% of the points summed for all programming exercises