Program to Search DNA Sequence in C And MIPS Assembly Language Assignment Solution

Instructions

Objective

Write a MIPS assignment program to search DNA sequence in and C.

Requirements and Specifications

DNA Search: This project explores pattern matching techniques to find a pattern in a DNA sequence containing letters in the DNA alphabet {A, C, G, T}. For example, suppose we have a DNA sequence as follows:

ATGACGATCTACGTATGGCAGCCACGCTTTTGATGTTAAGTCACACAGCCAAGTCAACAAGGGCGACTTCATGATCTTTCCGCTCCGTTGGTGTAGGCCCGTGTTCAAATTCAATGGCTGATTGGAATTACCTTTGAAATACTCCAACCGACCGCCACGGCCAGGGTCCCGCTCGCTCTCTGTGGCCCTCCCACAAAACTCCGGTGAAAGTTGATTTGGACACGGACCCAAAGCAGCGTAGATTATTCGAGCGTATTCGGTAGTCATTGAGGCCCCAA

The pattern “GCTTTT” can be found at index 27 (where the first letter of the sequence is at index 0). Note that overlapping matches are treated individually. For example, if the sequence is ‘AAAAAA’ and the pattern is ‘AAA’, there are 4 occurrences of the pattern: at indices 0, 1, 2, and 3. You will write a C program and a MIPS program to find the indices at which a given pattern occurs in a given DNA sequence.

Strategy: Unlike many “function only” programming tasks where a solution can be quickly envisioned and implemented, this task requires a different strategy.

1. Before writing any code, reflect on the task requirements and constraints. Mentally explore different approaches and algorithms, considering their potential performance and costs.The metrics of merit are static code length, dynamic execution time, and storage requirements. There are often trade offs between these parameters.
2. Once a promising approach is chosen, a high level language (HLL) implementation (e.g.,in C) can deepen its understanding. The HLL implementation is more flexible and convenient for exploring the solution space and should be written before constructing the assembly version where design changes are more costly and difficult to make. For P1-1, you will write a C implementation of the program.
3. Once a working C version is created, it’s time to “be the compiler” and see how it translates to MIPS assembly. This is an opportunity to see how HLL constructs are supported on a machine platform (at the ISA level). This level requires the greatest programming effort; but it also uncovers many new opportunities to increase performance and efficiency. You will write the assembly version for P1-2.

Screenshots of output

Source Code

C language /* ECE 2035 Project P1-1 Please fill in the following Student name: Current date: This is the only file that should be modified for the C implementation of Project 1. This program initializes a DNA sequence of 10,240 random characters and a pattern of 3 to 7 random characters, all characters are from the DNA alphabet {A, T, G, C}. For Project P1-1, you will implement the function Match, called by main. The function is defined at the end of this file. */ #include #include #include // DO NOT include any additional libraries. #define DEBUG 0 // RESET THIS TO 0 BEFORE SUBMITTING YOUR CODE #define SEQLEN 10240 #define MAXPATLEN 10 #define NUMCHAR 4 char Alphabet[] = "ACTG"; int MatchIndices[SEQLEN]; int main(int argc, char *argv[]) { char Seq[SEQLEN], Pat[MAXPATLEN]; int I, PatLen; void Print_Seq(char *Seq, int SeqLen); void Print_Pat(char *Pat, int PatLen); void Match(char *Pat, int PatLen, char *Seq, int SeqLen); if (DEBUG){ printf("Sample debugging print statement.\n"); } srand((unsigned int) time(NULL)); // seed random number generator PatLen = (rand() % MAXPATLEN) + 1; // compute pattern length for (I = 0; I < SEQLEN; I++) Seq[I] = Alphabet[rand() % NUMCHAR]; // create sequence for (I = 0; I < PatLen; I++) Pat[I] = Alphabet[rand() % NUMCHAR]; // create pattern Print_Pat(Pat, PatLen); // print pattern Print_Seq(Seq, SEQLEN); // print sequence Match(Pat, PatLen, Seq, SEQLEN); // match pattern in sequence printf("Pattern detected at the following locations:\n"); I = 0; while (MatchIndices[I] != -1) printf("Base pair %d in the sequence\n", MatchIndices[I++]); return 0; } /* Print Sequence This routine prints the sequence. */ void Print_Seq(char *Seq, int SeqLen) { int I; printf("The sequence is ...\n"); for (I = 0; I < SeqLen; I++) { putchar(Seq[I]); if (I % 80 == 79) printf("\n"); } } /* Print Pattern This routine prints the match pattern. */ void Print_Pat(char *Pat, int PatLen) { int I; printf("The pattern is ... \""); for (I = 0; I < PatLen; I++) putchar(Pat[I]); printf("\"\n"); } /* Match This routine find indices of occurrences of a variable length DNA pattern in a DNA sequence and stores them in the global array MatchIndices. It stores a -1 at MatchIndices[n] (where n = number of occurrences of the pattern) to indicate the end of the sequence of indices. */ void Match(char Pat[], int PatLen, char Seq[], int SeqLen) { // insert your code here MatchIndices[0] = -1; // replace this return; } Assembly language # DNA Search # # This program computes the indices of all (possibly overlapping) occurrences # of a pattern string in an input DNA sequence, given in the array starting # at the label Input. It stores the indices in the output array starting at # label Indices. # # Please fill in the following # Student name: # Date: .data Input: .alloc 600 Indices: .alloc 4800 .text DNAsearch: addi $1, $0, Input # point to input base swi 548 # create DNA search # your code goes here addi $1, $0, 5 # highlight position swi 549 addi $1, $0, 86 # highlight position swi 549 addi $1, $0, 167 # highlight position swi 549 addi $2, $0, 1 # store the output swi 580 # jr $31 # return to caller