Question

Programming language: Java

m: substring length

n: input strings

d: Hamming distance (mismatch)

I: Number of letters in Sample input string (s1, s2, s3)

Strings consists of: A, C, G, and T

Example outputs: Generate all possible possibilities of length m(4) using the values A, C, G, and T. EX possibilites: {A,A,A,A A,A,A,C.... G,G,G,G} and find all the possible combinations that have the same sequence with a hamming distance of 1 (only 1 difference)

Given n input strings of length l (i.e., there are l alphabets in each input string),

(a) develop an algorithm (i.e., a simple list of step-by-step recipe on how to create outputs from the given inputs) to find all substrings of length m that are common in all n input string with at most d mismatch (i.e., hamming distance of d). The set of possible alphabets in the input strings consists of A, C, G, and T.

Example #1: (n=3, l=10, m=4, and d=1)

Sample input strings: S1: ACTGACGCAG, S2: TCACAACGGG, and S3: GAGTCCAGTT

Expected Outputs: ACAG, CAGA, CCCA, and TCAG

Example #2: (n=3, l=10, m=4, and d=1)

Sample input strings: S1: GGAGGCCTGA, S2: TCAAGTCACA, and 3: GATCTTCAGG

Expected Outputs: AAGG, GGTC, GTCT, CAGA, CAGG, CATG, CCAG, CTCA

Answer 1

import java.util.Scanner;

public class JavaApplication {

  
// Hamming distance match or not
  
public static boolean getStringMatch(int n,int l,int m,int d,String [] s,String str){
boolean ret=false;
int count=0;// this part store the number of Hamming distance from every string
int d_=0;// count distance
  
  
// each string
  
for(int i=0;i<n;i++){
  
// store string
String curStr=s[i];
  
// each string match the substring of length m
for(int j=0;j<l-m+1;j++){
d_=0;
  
  
// match each character
for(int k=0;k<m;k++){
  
// if not match
// increase distance
if(curStr.charAt(j+k)!=str.charAt(k)){
d_++;
}
}
  
  
// if distance <d
// increase count and break
// because it is found
if(d_<=d){
  
count++;
break;
}
  
}
}
  
// finaly check str match with all strings
if(count==n){
ret=true;
}
  
  
return(ret);
}

  
  
public static void main(String[] args) {
  
// to input from user
  
Scanner sc= new Scanner(System.in);
  
int m,n,d,l;
  
System.out.print("Enter value of n : ");
n=sc.nextInt();
  
System.out.print("Enter value of l : ");
l=sc.nextInt();
  
System.out.print("Enter value of m : ");
m=sc.nextInt();
  
System.out.print("Enter value of d : ");
d=sc.nextInt();

// to store user inputs
  
String [] list=new String[n];
  
// user strings
for(int i=0;i<n;i++){
System.out.print("\nEnter input String "+(i+1)+" : ");
list[i]=sc.next();
  
}
sc.close();
  
// size of all combination of string of length m
int pVal=(int)Math.pow(m, m);
  
String [] combinations=new String[pVal];
  
// initialize
  
for(int i=0;i<pVal;i++){
combinations[i]="";
}
  
  
  
char [] chs=new char[4];
  
  
// each characters
chs[0]='A';
chs[1]='G';
chs[2]='C';
chs[3]='T';
  
// to index
  
int x=0,y=0,z=0,w=0;
  
// create combination of 4 characters
  
  
for(int i=0;i<pVal;i++){
  
  
// geting corresponding index
  
x=i/(int)Math.pow(m, 3);// for first index
y=(i/(int)Math.pow(m, 2))%4;// for 2 nd index
z=(i/m)%4;// for 3 rd index
w=i%4; // for last index
  
combinations[i]+=chs[x];
combinations[i]+=chs[y];
combinations[i]+=chs[z];
combinations[i]+=chs[w];
  
}
  
System.out.print("\n\nPossible outputs are : ");
  
// outputs
  
for(int i=0;i<pVal;i++){
  
  
// if distance found , then print
  
if(getStringMatch(n,l,m,d,list,combinations[i])==true){
System.out.print(combinations[i]+" ");
}
  
}
  
System.out.println();
}
  
}