Question

Use C++ promming language

In this assignment, you will implement a deterministic finite automata (DFA) using C++ programming language to extract matching patterns from a given input DNA sequence string.
1. Design a deterministic finite automata to recognize the regular expression A(A+T+G+C)*A + T(A+T+G+C)*T over the alphaber {A,T,G,C}. This regular expression recognize any string that starts and ends with ‘A’ or starts and ends with ‘T’.
2. 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 (1) to check if all possible substrings in the DNA sequence is a part of the regular expression or not. Below are two sample input/output. Only the bolded are user input. Use of external package or library for regular expression matching is not allowed.
example output:
Input a DNA sequence: CATTTGCAGGTG
Matching patterns are:
TT
TT
TTT
TTTGCAGGT
TTGCAGGT
TGCAGGT
ATTTGCA
Input a DNA sequence: TTTTAAAA
Matching patterns are:
AAAA
AAA
AA
TTTT
TTT TT

Answer 1

C++ CODE:

Step-by-step explanation:

#include <bits/stdc++.h>

using namespace std;

int countSubstringWithEqualEnds(string s)

{

int result = 0;

int n = s.length();

// Iterating through all substrings in

// way so that we can find first and last

// character easily

for (int i=0; i<n; i++)

for (int j=i+1; j<n; j++)

if (s[i] == s[j]) {

if(s[i] == 'A' || s[i] == 'T'){

result++;

for(int k=i;k<=j;k++){

cout << s[k];

}

cout << endl;

}

}

// result++;

return result;

}

// Driver function

int main()

{

string s;

cin >> s;

cout << "Total DFA matched strings::"<< countSubstringWithEqualEnds(s);

return 0;

}

***********************************************************************************************

OUTPUT: