# UVA Problem 1368 – DNA Consensus String Solution

UVA Problem 1368 – DNA Consensus String Solution:

Solving Technique:

Rank 174, Run time 12 ms ( 0.012 s ).

First input is number of test cases. Next of two inputs one is number of strings to input and another is the size of string. Our strings will only contain A, C, G, T characters.

For solving this problem we first need to find consensus string. That is of all strings we check each column of all strings and count the maximum occurring character in that column. This character is our consensus string character for that column.

Consensus string size is same as the input string size. Since each of its characters are maximum occurring characters in the input string. Example,

```TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
========
TAAGATAC    /* Consensus String, check each column for max character count */
```

Now that we have found the consensus string we just need to find consensus error. I will only explain the logic here, I have commented my code below.

```TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
========
TAAGATAC    /* Consensus String */
========
11101021    /* Consensus Error, 1+1+1+0+1+0+2+1 = 7, count every character of a column that don't match that consensus string character */
```

Now if you understood my explanation time to go write a better solution :).

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.

Input:

```3
5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA
6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA```

Output:

```TAAGATAC
7
ACGTACGTAA
6
AAGTTACCAA
12```

### Code:

```/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
* Problem: UVA 1368 ( DNA Consensus String )
*/

#include<stdio.h>

int main(){
register unsigned n, a, b, i, j, k, error;
scanf("%u", &n);

while(n--){
scanf("%u%u", &a, &b);

/**
* Create the string array
*/
char **s = new char*[a+1];
for(i = 0; i < a; ++i){
/**
* Allocate space for each string
*/
s[i] = new char[b+1];
/**
* Input a string in i th position
*/
scanf("%s", s[i]);
}

/**
* Consensus string declaration
*/
char *conseq = new char[b+1];
/**
* K is used below
*/
for(k = i = 0; i < b; ++i){
/**
* Reset A,C,G,T count array
*/
unsigned int seq = {0};
for(j = 0; j < a; ++j){
switch(s[j][i]){
case 65:    /* 65, 'A' here seq is A */
++seq;
break;
case 67:    /* 'C' */
++seq;
break;
case 71:    /* 'G' */
++seq;
break;
case 84:    /* 'T' */
++seq;
}
}

unsigned max = seq, maxIndex = 0;
for(j = 1; j < 4; ++j){
if(seq[j] > max){
/**
* Find the max count of A,C,G,T in a column, in all strings
*/
max = seq[j];
/**
* Remember the maxIndex for creating consensus string
*/
maxIndex = j;
}
}

/**
* We keep adding to our consensus string the most count of A,C,G,T
*/
switch(maxIndex){
case 0:
conseq[k++] = 65;
break;
case 1:
conseq[k++] = 67;
break;
case 2:
conseq[k++] = 71;
break;
case 3:
conseq[k++] = 84;
}
}

for(error = i = 0; i < b; ++i){
for(j = 0; j < a; ++j){
/**
* Calculate the error count by moving column by column of all strings, then comparing against the consensus string character in that column
*/
if(s[j][i] != conseq[i])
++error;
}
}

/**
* Print the consensus string and error count EACH ON A NEW LINE
*/
printf("%s\n%u\n", conseq, error);
}
return 0;
}
```