These two classes are not interacting like they should. When using the rabinKarp
ID: 3601757 • Letter: T
Question
These two classes are not interacting like they should. When using the rabinKarpHashes class and calling dnaSubstrand by passing pos and length to dnaSubstrand the substrand result I get back is not consitent on where the substrand starts and I am trying to use dnaSubstrand to create a new instance of a type DNA that only requires a string. They are in serperate classes but the dnaSubstrand class is public so that does not matter. Please help me figure out how to get a substrand back that is the same as is fed inside the rabinKarpHashes class.
package dna;
import java.util.Scanner;
/**
* Driver class for utilizing a DNA matcher.
* Retrieves Master DNA strand from user and as many match candidates as user wants to test.
*/
public class DNADriver
{
/**
* Scanner used for user input.
*/
private static Scanner in = new Scanner(System.in);
private java.lang.String input = "";
private static boolean end = true;
private static DNA temp;
private static java.lang.String tempString;
private static DNA temp2;
private static String strand;
/**
* Prompts user to enter a strand String for a new instance of DNA.
* @return Returns instance of DNA created from entered strand String, or null if "EXIT" entered.
*/
private static DNA inputDNAString()
{
while (true)
{
System.out.print("Molecule string DNA strand: ");
try
{
tempString = in.next();
if (tempString.equals("EXIT"))
{
return null;
}
temp = new DNA(tempString);
return temp;
}
catch (InvalidDNAStrandException e)
{
System.out.println(e + ", try again.");
}
}
}
//DO NOT make changes to main.
/**
* Entry point of execution. Runs DNA matching application.
* @param args Not used.
*/
public static void main(String[] args)
{
//Create DNA and DNAMatcher references
DNA master;
DNA candidate;
DNAMatcher matcher;
System.out.println("***Enter Master DNA***");
//Get DNA for the master strand
//Master DNA cannot be null, so continue until valid DNA is entered
do
{
master = inputDNAString();
}
while (master == null);
//Create the DNAMatcher with master DNA
matcher = new DNAMatcher(master);
System.out.println("***Enter DNA match candidates, EXIT to quit***");
//Accept candidate DNA until user quits
//inputDNAString will return null when "EXIT" is entered, so continue while null is not returned
while ((candidate = inputDNAString()) != null)
{
matcher.checkMatch(candidate);
}
//Output results!
System.out.println(" " + matcher);
}
}
package dna;
/**
* A DNA strand. Internally represented by a String containing only valid DNA molecules as follows:
*/
public class DNA
{
/**
* Numerical mapping of Adenine molecule.
*/
private static final char A_VALUE = 0;
/**
* Numerical mapping of Cytosine molecule.
*/
private static final char C_VALUE = 1;
/**
* Numerical mapping of Guanine molecule.
*/
private static final char G_VALUE = 2;
/**
* Numerical mapping of Thymine molecule.
*/
private static final char T_VALUE = 3;
/**
* Amount of possible distinct molecules in a DNA strand.
*/
public static final int ALLOWABLE_MOLECULES = 15;
/**
* Holds the molecule strand characters.
*/
private java.lang.String strandString;
/**
* DNA constructor. Accepts a String which represents the molecule sequence.
* @param strandIn Molecule sequence for this DNA.
*/
public DNA(java.lang.String strandIn)
{
setStrand(strandIn);
}
/**
* Returns the molecule sequence String.
* @return strandString String.
*/
public java.lang.String getStrand()
{
return strandString;
}
/**
* Returns the number of molecules in the DNA strand.
* @return Length of the DNA strand.
*/
public int getStrandLength()
{
return strandString.length();
}
/**
*
*/
@Override
public java.lang.String toString()
{
return "DNA Strand: " + this.getStrand();
}
/**
* Sets the strand String for this DNA.
* @param strandIn Desired strand String.
* @throws InvalidDNAStrandException Throws an InvalidDNAStrandException if incoming strand is invalid.
*/
private void setStrand(java.lang.String strandIn) throws InvalidDNAStrandException
{
char temp;
if (strandIn.length() > ALLOWABLE_MOLECULES)
{
throw new InvalidDNAStrandException();
}
else
{
for (int i = 0; i < strandIn.length(); i++)
{
temp = strandIn.charAt(i);
if (temp != 'A' && temp != 'C'
&& temp != 'T' && temp != 'G')
{
throw new InvalidDNAStrandException(temp);
}
}
this.strandString = strandIn;
}
}
/**
* Returns the hash value of the entire string for this DNA object.
* @return Hash of the string for this DNA object.
*/
public int dnaHash()
{
int q = 0;
int hash = 0;
for (int i = this.getStrandLength() - 1; i >= 0; i--)
{
char molecule = strandString.charAt(i);
//Magic number is to make it a base 4 system.
hash = (int) (hash + (charNumericValue(molecule) * Math.pow(4, q)));
q++;
}
return hash;
}
/**
* Given the character of a molecule, returns its numeric mapping.
* @param molecule Character of molecule.
* @return Numeric mapping of passed molecule character.
*/
public static int charNumericValue(char molecule)
{
switch (molecule)
{
case 'A':
return A_VALUE;
case 'C':
return C_VALUE;
case 'G':
return G_VALUE;
case 'T':
return T_VALUE;
default:
throw new InvalidDNAStrandException(molecule);
}
}
/**
* Generates and returns a new instance of DNA that is a substrand of this DNA.
* @param pos Beginning of the desired substrand of DNA.
* @param length Length of the desired substrand of DNA.
* @return New DNA that is a substrand of this DNA.
*/
public DNA dnaSubstrand(int pos, int length)
{
int count = 0;
//System.out.println("substrand test1 " + this.getStrand());
java.lang.String subString = this.getStrand().substring(pos, length);
//System.out.println("substrand test " + subString);
DNA sub = new DNA(subString);
//System.out.println("SUBSTRING FINAL: " + sub.getStrand());
return sub;
}
}
package dna;
/**
* Used to find the best sequential match for a DNA strand.
*/
public class DNAMatcher
{
/**
* Current best DNA match found.
*/
private DNA bestMatch;
/**
* Master strand of DNA to be matched.
*/
private DNA masterStrand;
/**
* Longest common substring match between master strand and current best match DNA.
*/
private DNA substrandMatch;
/**
* DNAMatcher constructor. Sets the master strand to the DNA passed.
* @param masterStrandIn Incoming master DNA strand for this DNAMatcher.
*/
public DNAMatcher(DNA masterStrandIn)
{
masterStrand = masterStrandIn;
bestMatch = null;
substrandMatch = null;
}
/**
* Returns the DNAMatcher's masterStrand.
* @return DNAMatcher's masterStrand.
*/
public DNA getMaster()
{
return masterStrand;
}
/**
* Returns the DNAMatcher's bestMatch.
* @return DNAMatcher's bestMatch.
*/
public DNA getBestMatch()
{
return bestMatch;
}
/**
* Formats this DNAMatcher into a String.
*/
@Override
public java.lang.String toString()
{
if (bestMatch == null)
{
return "Master: " + masterStrand + " NO MATCH FOUND";
}
else
{
return "Master: " + masterStrand
+ " Best Match: "
+ bestMatch
+ " Matching Substring: "
+ substrandMatch;
}
}
/**
* Given a DNA match candidate, checks if the passed DNA candidate has a
* longer common substring than is currently stored.
* @param matchCandidate Candidate for matching master strand.
*/
public void checkMatch(DNA matchCandidate)
{
String strand = matchCandidate.getStrand();
for (int i = strand.length(); i >= 1; i--)
{
for (int j = 0; j < strand.length(); j++)
{
int k = i + j;
if (k <= strand.length())
{
String temp = strand.substring(j, k);
if (temp.length() <= strand.length())
{
if (rabinKarp(matchCandidate) > -1)
{
temp = substrandMatch.getStrand();
bestMatch = matchCandidate;
}
}
}
}
}
}
/**
* Implements Rabin-Karp alogrithm for finding longest common substring.
* @param substrandCandidate DNA substrand to find in the master strand.
* @return Location in master strand if candidate substrand is found. If not found returns -1.
*/
private int rabinKarp(DNA substrandCandidate)
{
int substringHash = substrandCandidate.dnaHash();
int[] possibleHashes = new int[this.getMaster().getStrandLength()
- substrandCandidate.getStrandLength() + 1];
rabinKarpHashes(possibleHashes, 0, substrandCandidate.getStrandLength());
return linearSearchRecursive(possibleHashes, substringHash, 0);
}
/**
* Finds and stores the hash values of all substrings of passed size in the master strand.
* @param hashes Array of hashes to be populated.
* @param pos Current position in master strand's String to be hashed.
* @param length Length of the substrings in the master strand to be hashed.
* @return Returns the hash of the substring in the master strand at the given position of the given length.
*/
public int rabinKarpHashes(int[] hashes, int pos, int length)
{
int hash;
if (pos >= getMaster().getStrandLength() - length)
{
//System.out.println("MATCH TESTSER: " + getMaster().dnaSubstrand(pos, pos + length));
hash = (getMaster().dnaSubstrand(pos, pos + length)).dnaHash();
}
else
{
hash = rabinKarpHashes(hashes, pos + 1, length);
int next = DNA.charNumericValue(getMaster().getStrand().charAt(pos + length));
next *= Math.pow(4, length - 1);
hash -= next;
hash *= 4;
hash += DNA.charNumericValue(getMaster().getStrand().charAt(pos));
}
hashes[pos] = hash;
return hash;
}
/**
* Used to search through the string.
* @param data The current spot being searched.
* @param key What is being searched for.
* @param pos Which position is being searched.
* @return The found key value.
*/
private int linearSearchRecursive(int[] data, int key, int pos)
{
if (pos >= data.length)
{
return -1;
}
else if (data[pos] == key)
{
return pos;
}
else
{
return linearSearchRecursive(data, key, pos + 1);
}
}
}
package dna;
/**
* An unchecked Exception to be thrown when an illegal instance of DNA is attempted to be created.
*/
public class InvalidDNAStrandException extends java.lang.RuntimeException
{
/**
* Constructor used if DNA strand String is too long. Sets Exception message as "Strand too long"
*/
public InvalidDNAStrandException()
{
super("Strand too long");
}
/**
* Constructor used if DNA strand String contains an illegal molecule character.
* @param molecule Character of molecule that caused the strand to be invalid.
*/
public InvalidDNAStrandException(char molecule)
{
super("Invalid molecule: " + molecule);
}
}
Explanation / Answer
mport java.util.Scanner;
/**
* Driver class for utilizing a DNA matcher.
* Retrieves Master DNA strand from user and as many match candidates as user wants to test.
*/
public class DNADriver
{
/**
* Scanner used for user input.
*/
private static Scanner in = new Scanner(System.in);
private java.lang.String input = "";
private static boolean end = true;
private static DNA temp;
private static java.lang.String tempString;
private static DNA temp2;
private static String strand;
/**
* Prompts user to enter a strand String for a new instance of DNA.
* @return Returns instance of DNA created from entered strand String, or null if "EXIT" entered.
*/
private static DNA inputDNAString()
{
while (true)
{
System.out.print("Molecule string DNA strand: ");
try
{
tempString = in.next();
if (tempString.equals("EXIT"))
{
return null;
}
temp = new DNA(tempString);
return temp;
}
catch (InvalidDNAStrandException e)
{
System.out.println(e + ", try again.");
}
}
}
//DO NOT make changes to main.
/**
* Entry point of execution. Runs DNA matching application.
* @param args Not used.
*/
public static void main(String[] args)
{
//Create DNA and DNAMatcher references
DNA master;
DNA candidate;
DNAMatcher matcher;
System.out.println("***Enter Master DNA***");
//Get DNA for the master strand
//Master DNA cannot be null, so continue until valid DNA is entered
do
{
master = inputDNAString();
}
while (master == null);
//Create the DNAMatcher with master DNA
matcher = new DNAMatcher(master);
System.out.println("***Enter DNA match candidates, EXIT to quit***");
//Accept candidate DNA until user quits
//inputDNAString will return null when "EXIT" is entered, so continue while null is not returned
while ((candidate = inputDNAString()) != null)
{
matcher.checkMatch(candidate);
}
//Output results!
System.out.println(" " + matcher);
}
}
package dna;
/**
* A DNA strand. Internally represented by a String containing only valid DNA molecules as follows:
*/
public class DNA
{
/**
* Numerical mapping of Adenine molecule.
*/
private static final char A_VALUE = 0;
/**
* Numerical mapping of Cytosine molecule.
*/
private static final char C_VALUE = 1;
/**
* Numerical mapping of Guanine molecule.
*/
private static final char G_VALUE = 2;
/**
* Numerical mapping of Thymine molecule.
*/
private static final char T_VALUE = 3;
/**
* Amount of possible distinct molecules in a DNA strand.
*/
public static final int ALLOWABLE_MOLECULES = 15;
/**
* Holds the molecule strand characters.
*/
private java.lang.String strandString;
/**
* DNA constructor. Accepts a String which represents the molecule sequence.
* @param strandIn Molecule sequence for this DNA.
*/
public DNA(java.lang.String strandIn)
{
setStrand(strandIn);
}
/**
* Returns the molecule sequence String.
* @return strandString String.
*/
public java.lang.String getStrand()
{
return strandString;
}
/**
* Returns the number of molecules in the DNA strand.
* @return Length of the DNA strand.
*/
public int getStrandLength()
{
return strandString.length();
}
/**
*
*/
@Override
public java.lang.String toString()
{
return "DNA Strand: " + this.getStrand();
}
/**
* Sets the strand String for this DNA.
* @param strandIn Desired strand String.
* @throws InvalidDNAStrandException Throws an InvalidDNAStrandException if incoming strand is invalid.
*/
private void setStrand(java.lang.String strandIn) throws InvalidDNAStrandException
{
char temp;
if (strandIn.length() > ALLOWABLE_MOLECULES)
{
throw new InvalidDNAStrandException();
}
else
{
for (int i = 0; i < strandIn.length(); i++)
{
temp = strandIn.charAt(i);
if (temp != 'A' && temp != 'C'
&& temp != 'T' && temp != 'G')
{
throw new InvalidDNAStrandException(temp);
}
}
this.strandString = strandIn;
}
}
/**
* Returns the hash value of the entire string for this DNA object.
* @return Hash of the string for this DNA object.
*/
public int dnaHash()
{
int q = 0;
int hash = 0;
for (int i = this.getStrandLength() - 1; i >= 0; i--)
{
char molecule = strandString.charAt(i);
//Magic number is to make it a base 4 system.
hash = (int) (hash + (charNumericValue(molecule) * Math.pow(4, q)));
q++;
}
return hash;
}
/**
* Given the character of a molecule, returns its numeric mapping.
* @param molecule Character of molecule.
* @return Numeric mapping of passed molecule character.
*/
public static int charNumericValue(char molecule)
{
switch (molecule)
{
case 'A':
return A_VALUE;
case 'C':
return C_VALUE;
case 'G':
return G_VALUE;
case 'T':
return T_VALUE;
default:
throw new InvalidDNAStrandException(molecule);
}
}
/**
* Generates and returns a new instance of DNA that is a substrand of this DNA.
* @param pos Beginning of the desired substrand of DNA.
* @param length Length of the desired substrand of DNA.
* @return New DNA that is a substrand of this DNA.
*/
public DNA dnaSubstrand(int pos, int length)
{
int count = 0;
//System.out.println("substrand test1 " + this.getStrand());
java.lang.String subString = this.getStrand().substring(pos, length);
//System.out.println("substrand test " + subString);
DNA sub = new DNA(subString);
//System.out.println("SUBSTRING FINAL: " + sub.getStrand());
return sub;
}
}
package dna;
/**
* Used to find the best sequential match for a DNA strand.
*/
public class DNAMatcher
{
/**
* Current best DNA match found.
*/
private DNA bestMatch;
/**
* Master strand of DNA to be matched.
*/
private DNA masterStrand;
/**
* Longest common substring match between master strand and current best match DNA.
*/
private DNA substrandMatch;
/**
* DNAMatcher constructor. Sets the master strand to the DNA passed.
* @param masterStrandIn Incoming master DNA strand for this DNAMatcher.
*/
public DNAMatcher(DNA masterStrandIn)
{
masterStrand = masterStrandIn;
bestMatch = null;
substrandMatch = null;
}
/**
* Returns the DNAMatcher's masterStrand.
* @return DNAMatcher's masterStrand.
*/
public DNA getMaster()
{
return masterStrand;
}
/**
* Returns the DNAMatcher's bestMatch.
* @return DNAMatcher's bestMatch.
*/
public DNA getBestMatch()
{
return bestMatch;
}
/**
* Formats this DNAMatcher into a String.
*/
@Override
public java.lang.String toString()
{
if (bestMatch == null)
{
return "Master: " + masterStrand + " NO MATCH FOUND";
}
else
{
return "Master: " + masterStrand
+ " Best Match: "
+ bestMatch
+ " Matching Substring: "
+ substrandMatch;
}
}
/**
* Given a DNA match candidate, checks if the passed DNA candidate has a
* longer common substring than is currently stored.
* @param matchCandidate Candidate for matching master strand.
*/
public void checkMatch(DNA matchCandidate)
{
String strand = matchCandidate.getStrand();
for (int i = strand.length(); i >= 1; i--)
{
for (int j = 0; j < strand.length(); j++)
{
int k = i + j;
if (k <= strand.length())
{
String temp = strand.substring(j, k);
if (temp.length() <= strand.length())
{
if (rabinKarp(matchCandidate) > -1)
{
temp = substrandMatch.getStrand();
bestMatch = matchCandidate;
}
}
}
}
}
}
/**
* Implements Rabin-Karp alogrithm for finding longest common substring.
* @param substrandCandidate DNA substrand to find in the master strand.
* @return Location in master strand if candidate substrand is found. If not found returns -1.
*/
private int rabinKarp(DNA substrandCandidate)
{
int substringHash = substrandCandidate.dnaHash();
int[] possibleHashes = new int[this.getMaster().getStrandLength()
- substrandCandidate.getStrandLength() + 1];
rabinKarpHashes(possibleHashes, 0, substrandCandidate.getStrandLength());
return linearSearchRecursive(possibleHashes, substringHash, 0);
}
/**
* Finds and stores the hash values of all substrings of passed size in the master strand.
* @param hashes Array of hashes to be populated.
* @param pos Current position in master strand's String to be hashed.
* @param length Length of the substrings in the master strand to be hashed.
* @return Returns the hash of the substring in the master strand at the given position of the given length.
*/
public int rabinKarpHashes(int[] hashes, int pos, int length)
{
int hash;
if (pos >= getMaster().getStrandLength() - length)
{
//System.out.println("MATCH TESTSER: " + getMaster().dnaSubstrand(pos, pos + length));
hash = (getMaster().dnaSubstrand(pos, pos + length)).dnaHash();
}
else
{
hash = rabinKarpHashes(hashes, pos + 1, length);
int next = DNA.charNumericValue(getMaster().getStrand().charAt(pos + length));
next *= Math.pow(4, length - 1);
hash -= next;
hash *= 4;
hash += DNA.charNumericValue(getMaster().getStrand().charAt(pos));
}
hashes[pos] = hash;
return hash;
}
/**
* Used to search through the string.
* @param data The current spot being searched.
* @param key What is being searched for.
* @param pos Which position is being searched.
* @return The found key value.
*/
private int linearSearchRecursive(int[] data, int key, int pos)
{
if (pos >= data.length)
{
return -1;
}
else if (data[pos] == key)
{
return pos;
}
else
{
return linearSearchRecursive(data, key, pos + 1);
}
}
}
package dna;
/**
* An unchecked Exception to be thrown when an illegal instance of DNA is attempted to be created.
*/
public class InvalidDNAStrandException extends java.lang.RuntimeException
{
/**
* Constructor used if DNA strand String is too long. Sets Exception message as "Strand too long"
*/
public InvalidDNAStrandException()
{
super("Strand too long");
}
/**
* Constructor used if DNA strand String contains an illegal molecule character.
* @param molecule Character of molecule that caused the strand to be invalid.
*/
public InvalidDNAStrandException(char molecule)
{
super("Invalid molecule: " + molecule);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.