Minimum Genetic Mutation

Problem Statement

In computational biology, gene sequences are made up of characters from the set {'A', 'C', 'G', 'T'}. Each character represents a nucleotide, and a gene can be represented as a sequence of these nucleotides. In our problem, we deal with gene sequences that are always 8 characters long.

The goal is to determine the smallest number of mutations required to transform one given gene string (startGene) into another (endGene). A single mutation is defined as changing exactly one character in the gene string to a different character from the set {'A', 'C', 'G', 'T'}.

However, not all potential mutations are valid. Valid mutations are explicitly listed in a given bank array — a mutation to a gene sequence not present in this bank is not allowed. If no sequence of valid mutations can convert the startGene into the endGene, the function should return -1.

An important aspect of the problem is that while the starting gene sequence must be valid to consider, it doesn't necessarily have to be included in the bank. Each sequence (whether startGene or sequences in the bank) is precisely 8 characters long, consisting only of the characters {'A', 'C', 'G', 'T'}.

Examples

Example 1

Input:

startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]

Output:

1

Example 2

Input:

startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]

Output:

2

Constraints

• 0 <= bank.length <= 10
• startGene.length == endGene.length == bank[i].length == 8
• startGene, endGene, and bank[i] consist of only the characters ['A', 'C', 'G', 'T'].

Approach and Intuition

The mutation problem can be visualized as a graph traversal problem where:

• Each gene string in the bank (including potentially the startGene and endGene if they are in the bank) represents a node in the graph.
• An edge exists between two gene strings if they differ by exactly one mutation.

The objective is to find the shortest path from the startGene to the endGene within this graph. Here’s a step-by-step breakdown of the approach:

1. Graph Construction:

   • Start by adding startGene and endGene to the graph nodes if they are part of the bank.
   • Generate edges between all pairs of nodes where the nodes differ by exactly one mutation.

2. Breadth-First Search (BFS):

   • Use BFS to find the shortest path from the startGene to the endGene. BFS is suitable because it explores nodes layer by layer, ensuring that the first time it reaches endGene, it has found the shortest path.
   • Begin the BFS from the startGene, and at each step, attempt all possible valid mutations that are one character different and exist within the bank.
   • Track the visited nodes to prevent cycles and redundant work.

3. Early Exit:

   • If you can mutate startGene directly to endGene in the bank, return 1.
   • If the BFS completes without reaching the endGene, return -1 as it indicates there's no valid path of mutations.

This method leverages BFS for its natural applicability to shortest-path problems in unweighted graphs. By navigating through the explicitly allowed mutations (edges), the algorithm efficiently finds or refutes the possibility of transforming startGene into endGene through legal mutations.

Solutions

class Solution {
public:
    int leastMutations(string startSequence, string endSequence, vector<string>& geneBank) {
        queue<string> planQueue;
        unordered_set<string> visited;
        planQueue.push(startSequence);
        visited.insert(startSequence);
            
        int mutationCount = 0;
        while (!planQueue.empty()) {
            int levelSize = planQueue.size();
                
            for (int level = 0; level < levelSize; level++) {
                string current = planQueue.front();
                planQueue.pop();
    
                if (current == endSequence) {
                    return mutationCount;
                }
                    
                for (char gene : "ACGT") {
                    for (int pos = 0; pos < current.size(); pos++) {
                        string mutated = current;
                        mutated[pos] = gene;
                        if (!visited.count(mutated) && find(geneBank.begin(), geneBank.end(), mutated) != geneBank.end()) {
                            planQueue.push(mutated);
                            visited.insert(mutated);
                        }
                    }
                }
            }
                
            mutationCount++;
        }
            
        return -1;
    }
};