Activity 3. A Glimpse at Sequence Analysis. (Inspired by Problem Set 3 from MIT
ID: 3687071 • Letter: A
Question
Activity 3. A Glimpse at Sequence Analysis.
(Inspired by Problem Set 3 from MIT OpenCourseWare, made available on Google’s EngageCSEdu)
String matching is very valuable in settings such as biology. A common problem in modern biology is to understand the structure of DNA molecules, and the role of specific structures in determining the function of the molecule. A DNA sequence is commonly represented as a sequence of one of four nucleotides – adenine (A), cytosine (C), guanine (G), or thymine (T) –and hence a DNA molecule or strand is represented by a string composed of elements from an alphabet of only four symbols, for example, the string AAACAACTTCGTAAGTATA represents a particular strand of DNA.
One way to understand the function of a particular strand of DNA (or even a sub-strand of DNA) is to match that strand against a library of known DNA sequences – that is, sequences whose function and structure is known – with the idea that similar structure tends to imply similar function. Simple organisms such as bacteria may have millions of nucleotides in their DNA sequence, and the human chromosome is believed to have on the order of 246 million bases, so any matching scheme must be very efficient in order to be useful.
In this activity, we hope to give you a sense of some of the issues involved, by exploring some simple matching schemes. We are asking you to program the following functionalities:
Methods 1 & 2: isDNA-Iter and isDNA-Rec
Parameter: a string str
Return type: a boolean
This method returns true if the string str contains only characters A, T, G, C, false otherwise
Note: You have to implement two methods for this one functionality: one iterative method and one recursive method.
Methods 1 and 2: one iterative and one recursive, for the same functionality:
Method 3: you are free to implement it iteratively or recursively.
Method 3: lastIndexSubStringMatch
Parameter: a key string, a target string, and an integer index
Return type: an integer
This method checks if the key string appears in the target string after (including) character at location index.
It will return the last index of the first occurrence if the key string does appear in the target string after location index.
It will return -1 otherwise.
Example 1:
lastIndexSubStringMatch("atgc","atgacatgcacaagtatgcat",3) should return: 8.
because “atgc” appears in the target string starting at location 5 and ends at location 8.
A
T
G
A
C
A
T
G
C
A
C
A
A
G
T
A
T
G
C
A
T
index
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A
T
G
C
We see that we matched “atgc” to a substring of the target string, starting at an index equal to or larger than 3 (all smaller indices were grayed), and the last index of this substring is 8: this is what the method needs to return.
Note: “atgc” appears later in the target string (between indices 15 and 18) but your method “lastIndexSubStringMatch” only looks at the first occurrence of the key string.
Example 2:
lastIndexSubStringMatch("atga","atgacatgcacaagtatgcat",3) should return: -1.
because “atga” appears in the target string only starting at location 0, which is before the index parameter (=3).
Methods 4 and 5: one iterative and one recursive, for the same functionality.
Methods 4 & 5: countSubStringMatch-Iter and countSubStringMatch-Rec
Parameter: a key string and a target string
Return type: an integer, which is the number of instances of the key string in the target string.
Note: //You have to implement two methods for this one functionality: one iterative method and one recursive method.
Example 1:
countSubStringMatch("atgc","atgacatgcacaagtatgcat") should return: 2.
because “atgc” appears in the target string starting at location 5 and at location 15.
A
T
G
A
C
A
T
G
C
A
C
A
A
G
T
A
T
G
C
A
T
index
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A
T
G
C
A
T
G
C
/******************************* ACTIVITY 3 ************************************/
/*******************************************************************************/
/*********************** isDNA: Iter and Rec ***********************************/
// Iterative version
public static boolean isDNAIter(String str) {
}
// Recursive version
public static boolean isDNARec(String str) {
}
/*********************** lastIndexSubStringMatch *******************************/
public static int lastIndexSubStringMatch(String key, String target, int index) {
}
/*********************** countSubStringMatch: Iter and Rec *********************/
// Iterative version
public static int countSubStringMatchIter(String key, String target) {
}
// Recursive version
public static int countSubStringMatchRec(String key, String target) {
}
Methods 1 & 2: isDNA-Iter and isDNA-Rec
Parameter: a string str
Return type: a boolean
This method returns true if the string str contains only characters A, T, G, C, false otherwise
Note: You have to implement two methods for this one functionality: one iterative method and one recursive method.
Explanation / Answer
import java.io.*;
import java.util.*;
import java.lang.*;
public static boolean isDNAIter(String str) {
int index,n;
char ch;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println(“enter index:”);
index = br.readLine();
System.out.println(“Enter no of indexes:”);
n = br.readLine();
for(index : 1 to n) {
ch = str.charAt(index);
if(ch == ‘A’ || ch==’T’ || ch==’G’ || ch==’C’)
return true;
else return false;
}
}
public static boolean isDNARec(String str) {
int index;
char ch;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Systrm.out.println(“enter index:”);
index = br.readLine();
ch = str.charAt(index);
if(ch == ‘A’ || ch==’T’ || ch==’G’ || ch==’C’)
return true;
else return false;
boolen isDNARec(String str) +1;
}
public static int lastIndexSubStringMatch(String key,String target,int index) {
Boolean f;
int n;
int t;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println(“Enter no of indexes:”);
n= br.readLine();
for(index: 1 to n) {
f = key.matches(target,index);
if(f==”true”) {
t=key.lastIndexOf(target);
return t;
}
else return -1;
}
}
public static int countSubStringMatchIter(String key,String target) {
int count = 0;
int lastIndex =0;
while (lastIndex!=-1) {
lastIndex= str.index(key,target);
if(lastIndex !=-1) {
count = count++;
lastIndex + = key.length();
}
}
return count;
}
public static int countSubStringMatchRec(String key,String target) {
int count = 0;
int index;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Syste.out.println(“Enter index:”);
index = br.readLine();
if(key.length() <4)
return 0;
else
{ if(key.substring(index) == target) {
count = count ++;
return countSubStringMatchRec(key.substring(index),target) +1; }
else return countSubStringMatchRec(key.substring(index),target);
}
return count;
}
public class DNA {
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int ch;
System.out.println(“Enter choice:”);
ch = br.readLine();
string key,target;
System.out.println(“Enter string”);
key = br.readLine();
System.out.println(“Enter substring”);
target = br.readLine();
switch(ch) {
case 1: System.out.println(“DNA - Iteration”);
String str;
System.out.println(“Enter string”);
str = br.readLine();
boolean isDNAIter(String str);
break;
case 2: System.out.println(“DNA – Recursion”);
String str;
System.out.println(“Enter string”);
str = br.readLine();
boolean isDNAREC(String str);
break;
case 3: System.out.println(“Last index of substring match”);
int index;
System.out.println(“Enter index”);
index = br.readLine();
int lastIndexSubStringMatch(String key,String target,ont index);
System.out.println(“Last index:” + t );
break;
case 4: System.out.println(“Counting substrings - Iteration”);
int countSubStringMatchIter(String key,String target);
System.out.println(“count:” +count);
break;
case 5: System.out.println(“Counting substrings – Recursion”);
int countSubStringMatchRec(String key,String target);
System.out.println(“count:” +count);
break;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.