Algorithm Homework

Closed Posted Nov 28, 2003 Paid on delivery
Closed 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

C Programming Engineering MySQL PHP Software Architecture Software Testing

Project ID: #3020930

About the project

7 proposals Remote project Active Dec 21, 2003

7 freelancers are bidding on average $48 for this job

mihaiscortaru

See private message.

$121.13 USD in 4 days
(160 Reviews)
6.0
carefulwith

See private message.

$33.15 USD in 4 days
(13 Reviews)
3.1
andreeamvw

See private message.

$42.5 USD in 4 days
(7 Reviews)
3.0
eyenetsolut

See private message.

$17 USD in 4 days
(14 Reviews)
2.5
mihaichiru

See private message.

$8.5 USD in 4 days
(4 Reviews)
1.9
vw965016vw

See private message.

$85 USD in 4 days
(2 Reviews)
0.2
andyuvw

See private message.

$25.5 USD in 4 days
(0 Reviews)
0.0