Algorithm Homework
$30-5000 USD
Paid on delivery
Quest for Keres
-------------------------------------------------------------The Story
Professor Droso is performing a genetical study of a reproduction gene
Cytherea across different species. For each species, he has even, after much
pain, obtained mutant forms of this gene. But, come to believe it,
Elegan --a newcomer student working in the lab, who happens to be your dear
friend-- has labelled all the vials with non-permanent marker. He has also
mixed-in a vial from the Keres-gene experiment into the Cytherea batch.
After giving the vials a warm bath, Elegan notices that all the labels are
wiped off, and that he has an extra vial which must be containing a mutant
Keres. Luckily, Professor Droso is away for a conference, and Elegan decides
to at least find out which vial does not belong to the Cytherea batch. He
runs a sample from each vial through sequence analysis, and obtains the DNA
sequences. But, by looking at these sequences, he just can't tell which.
Your friend Elegan asks your help for finding the foreign Keres gene. You
tell him to calm down, because you can use the Minimum Spanning Tree
algorithm you have just learnt, to find out the Keres gene.
Your Task
You are given a set of DNA sequences and your goal is to remove one of these
sequences such as to minimize the total length of the minimum spanning tree
you can construct for these sequences. As the distance metric between two
sequences, use the minimum edit distance between them. For the edit distance
measure, you should use only copy, insert, delete, and replace operations
(whose costs are 0, 1, 1, 1, respectively).
Input
Your program will read the input data from a file named keres.inp. The file
will contain a number N (1<=N<=100), followed by N genetic sequences (each
with a max-length of 1000), one on each line. You can assume that the input
is error-free.
[url removed, login to view]
4
ATTACATGCG
ATGAGATCCC
CTTACATGCGG
ATTACATTCG
Output
Output of your program is a file named keres.out. It must contain a single
line with two integer numbers, giving the index of the foreign gene you find
(indexes start with 0), followed by the total distance of the minimum
spanning tree you obtain by removing this gene.
[url removed, login to view]
1 3
Submission
You will submit your source file keres.c (or [url removed, login to view]).
Good luck!
## Deliverables
1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.
2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request.
3) Exclusive and complete copyrights to all work purchased. (No GPL, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site).
## Platform
PII 450
Must run in less then 30 seconds
Linux
Project ID: #3020930