Question

In this assignment, you will implement a deterministic finite automata (DFA) using C++ programming language to extract all matching patterns (substrings) from a given input DNA sequence string.

1. The alphabet for generating DNA sequences is {A, T, G, C}. Write a regular expression that represents all DNA strings that contains at least two ‘A’s. Note: assume empty string is not a valid string.

2. Design a deterministic finite automaton to recognize the regular expression.

3. Write a program which asks the user to input a DNA sequence. The program should be able to extract all the patterns (substrings present in the DNA sequence) that match the regular expression given in 1. You MUST implement DFA from (2) to check if all possible substrings in the DNA sequence is a part of the regular expression or not.

Note: even if the same pattern is found multiple times, it should be printed every time it is found.

Below are two sample input/output. Only the bolded are user input.

Input a DNA sequence: CATTTGCAGG

Matching patterns are:

CATTTGCA

CATTTGCAG

CATTTGCAGG

ATTTGCA

ATTTGCAG

ATTTGCAGG

Input a DNA sequence: TTTATAA

Matching patterns are:

TTTATA

TTTATAA

TTATA

TTATAA

TATA

TATAA

ATA

ATAA

TAA

AA

What to submit:

1. Submit a digital copy of the regular expression and diagram of the DFA.

2. Submit a cpp file representing your program (just send the code I will paste the code in myself)

Answer 1

REGULAR EXPRESSION:-  

For alphabet generating DNA sequences {A, T, G, C}

(T+G+C)*A(T+G+C)*A(A+T+G+C)*

DFA:-

PROGRAM:

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

void subString(char str[], int n)
{
//declaring the temporary stringvariable
string temp;
//declaring the variable count
int count;
// Pick starting point
for (int len = 1; len <= n; len++) //loop from 1 to length of string
{
// Pick ending point
for (int i = 0; i <= n - len; i++)
{
// Print characters from current
// starting point to current ending
// point.

int j = i + len - 1;
//emptying the temporary variable
temp.clear();
//count to zero
count=0;
for (int k = i; k <= j; k++)
{
//concatenating each letter to temporary variable
temp+=str[k];
//if the letter is 'a' or 'A'
//then increment count by one
if (str[k]=='a' || str[k]=='A')
count=count+1;
}
// if count is atleast two
//print corresponding string
if(count>=2)
cout << temp << endl;
}
}
}
int main()
{
string str;
cout << "INPUT A DNA SEQUENCE: ";
//reading dna sequence
//storing it in str
cin >> str;

//converting string to char array
//declaring cstr by assigning (size of str size + 1)
char cstr[str.size() + 1];
//copying string from str to cstr
str.copy(cstr, str.size() + 1);
//setting end of char array cstr
cstr[str.size()] = '\0';

//calling the method to find subString
//having atleast 2 'a'
subString(cstr,strlen(cstr));
return 0;
}

PROGRAM FILE:-

OUTPUT:-