Algorithm Homework

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. [login to view URL] 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. [login to view URL] 1 3 Submission You will submit your source file keres.c (or [login to view URL]). 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