A gene string can be represented by an 8-character long string, with choices fro

Question

A gene string can be represented by an 8-character long string, with choices from "A", "C", "6", "I". Suppose *r need to investigate about a mutation (mutation from 'start' to "end"), where ONE mutation is defined as ONE single character For example, "AACCGGTT" rightarrow "AACCGGTA" is 1 mutation. Also, there is a given gene "bank", which records all the valid gene notations. A gene must be in the bark to awake it a valid gene string. Now, given 3 things - start, cod, bank, your task is to determine what is the minimum number of Mutations needed to mutate from "start" to If there is no such a mutation, return -1. If the start and end string are the same, return 0. Example: start: "AACCGGTT" end: "AAACGGTA" bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"] return: 2 Organize your solution into a driver class (with a main method) and utility class containing the logical implementation. Points will be docked for code that's too tightly coupled.

Explanation / Answer

Below is your code: -

GenericMutationDriver.java

public class GenericMutationDriver {
   public static void main(String[] args) {
       // initializing variables to check mutation distance
       String start = "AACCGGTT";
       String end = "AAACGGTA";
       String[] bank = { "AACCGGTA", "AACCGCTA", "AAACGGTA" };

       System.out.println("Mutation distance between two gene strings are: "
               + GeneMutationUtility.getMutationDistance(start, end, bank));
   }
}

GeneMutationUtility.java

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class GeneMutationUtility {
   // Getting mutation distance using BFS algorithm
   public static int getMutationDistance(String start, String end, String[] bank) {
       if (start.equals(end)) // if start and end gene is already same then
                               // return distance zero
           return 0;

       // Adding all bank items in a HashSet, it will help to compare the
       // mutated string to bank item
       Set<String> bankSet = new HashSet<>();
       for (String b : bank)
           bankSet.add(b);

       // valid genes allowed are A,C,G,T
       char[] validGeneSet = new char[] { 'A', 'C', 'G', 'T' };

       // distance between two gene strings
       int distance = 0;

       // check mutations which are already processed(processeStrings) and new
       // ones(stringQueue)
       Set<String> processeStrings = new HashSet<>();
       Queue<String> stringQueue = new LinkedList<>();
       stringQueue.offer(start);
       processeStrings.add(start);

       // until the whole string is traversed and checked
       while (!stringQueue.isEmpty()) {
           int size = stringQueue.size(); // getting the length of the string
           while (size-- > 0) {
               String currentString = stringQueue.poll(); // getting the top
                                                           // elements of queue
               if (currentString.equals(end)) // if after mutation current
                                               // becomes equal
                   // to end string, then return distance.
                   // This is the main result step of the
                   // loop
                   return distance;

               // mutating the string by converting it to array and then
               // changing one char at a time.
               char[] currentStringToArray = currentString.toCharArray();
               for (int i = 0; i < currentStringToArray.length; i++) {
                   char oldChar = currentStringToArray[i]; // saving the old
                                                           // char
                   for (char c : validGeneSet) { // replacing char with another
                                                   // valid char one at a time
                       currentStringToArray[i] = c;
                       String mutatedString = new String(currentStringToArray);// after
                                                                               // replacing
                       // one char forming
                       // a string
                       // if the new string is present in bankSet, then add it
                       // visited and queue
                       if (!processeStrings.contains(mutatedString) && bankSet.contains(mutatedString)) {
                           processeStrings.add(mutatedString);
                           stringQueue.offer(mutatedString);
                       }
                   }
                   // after adding to bank and visited set, change the
                   // character to old one and then check the next character in
                   // string
                   currentStringToArray[i] = oldChar;
               }
           }
           // after each iteration, increment the distance.
           distance++;
       }
       // if even after each mutation tested, string didn't matched the end
       // string, return -1
       return -1;
   }
  
}

Sample Run: -

Mutation distance between two gene strings are: 2

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.