Skip to Content
CoursesCSC102การหาจำนวนการกลายพันธุ์น้อยที่สุดของยีน

การหาจำนวนการกลายพันธุ์น้อยที่สุดของยีน

โจทย์

A gene string can be represented by an 8-character long string, with choices from ‘A’, ‘C’, ‘G’, and ‘T’.

Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.

For example, “AACCGGTT” —> “AACCGGTA” is one mutation.

There is also a gene bank that records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Given the two gene strings startGene and endGene and the gene bank, return the minimum number of mutations needed to mutate from startGene to endGene. If there is no such mutation, return -1.

Note that the starting point is assumed to be valid, so it might not be included in the bank but the end gene must be in the bank.

InputOutput
AACCGTTT
AACCGGTA
1
AACCGGTT		-1
AACCGTTT
AACCGGTA
2
AACCGGTA
AACCGGTT		2

โค้ด

import java.util.Scanner;
 
public class Program {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        String startGene = scanner.next();
        String endGene = scanner.next();
        int bankAmount = scanner.nextInt();
 
        String[] geneBank = new String[bankAmount];
        for (int i = 0; i < bankAmount; i++) {
            geneBank[i] = scanner.next();
        }
 
        boolean isEndGenePresent = false;
        for (String gene : geneBank) {
            if (gene.equals(endGene)) {
                isEndGenePresent = true;
                break;
            }
        }
        if (!isEndGenePresent) {
            System.out.println(-1);
            return;
        }
 
        String[] queue = new String[bankAmount + 1];
        int front = 0, rear = 0;
        queue[rear++] = startGene;
 
        boolean[] visited = new boolean[bankAmount];
 
        int mutationCount = 0;
        char[] charChoices = {'A', 'C', 'G', 'T'};
        while (front < rear) {
            int currentLevelSize = rear - front;
            mutationCount++;
 
            for (int i = 0; i < currentLevelSize; i++) {
                String currentGene = queue[front++];
 
                for (int j = 0; j < currentGene.length(); j++) {
                    char[] geneChars = currentGene.toCharArray();
 
                    for (char c : charChoices) {
                        if (geneChars[j] != c) {
                            geneChars[j] = c;
                        }
 
                        String mutatedGene = new String(geneChars);
 
                        if (mutatedGene.equals(endGene)) {
                            System.out.println(mutationCount);
                            return;
                        }
 
                        for (int k = 0; k < bankAmount; k++) {
                            if (!visited[k] && geneBank[k].equals(mutatedGene)) {
                                queue[rear++] = mutatedGene;
                                visited[k] = true;
                            }
                        }
 
                        geneChars[j] = currentGene.charAt(j);
                    }
                }
            }
        }
 
        System.out.println(-1);
    }
}

คำอธิบาย

1. การตรวจสอบเงื่อนไขเบื้องต้น

// ตรวจสอบว่ายีนเป้าหมายอยู่ใน bank หรือไม่
boolean isEndGenePresent = false;
for (String gene : geneBank) {
    if (gene.equals(endGene)) {
        isEndGenePresent = true;
        break;
    }
}
if (!isEndGenePresent) {
    System.out.println(-1);
    return;
}
String[] queue = new String[bankAmount + 1];  // คิวเก็บยีนที่จะตรวจสอบ
int front = 0, rear = 0;                      // ตัวชี้หน้าและหลังคิว
queue[rear++] = startGene;                    // ใส่ยีนเริ่มต้นลงในคิว
boolean[] visited = new boolean[bankAmount];   // เก็บสถานะการเยี่ยม
char[] charChoices = {'A', 'C', 'G', 'T'};    // ตัวเลือกสำหรับการกลายพันธุ์

3. การค้นหาด้วย BFS

while (front < rear) {  // ยังมียีนที่ต้องตรวจสอบ
    int currentLevelSize = rear - front;  // จำนวนยีนในระดับปัจจุบัน
    mutationCount++;                      // เพิ่มจำนวนการกลายพันธุ์
 
    // ตรวจสอบทุกยีนในระดับปัจจุบัน
    for (int i = 0; i < currentLevelSize; i++) {
        String currentGene = queue[front++];
 
        // ลองเปลี่ยนแต่ละตำแหน่ง
        for (int j = 0; j < currentGene.length(); j++) {
            char[] geneChars = currentGene.toCharArray();
 
            // ลองแต่ละตัวอักษรที่เป็นไปได้
            for (char c : charChoices) {
                if (geneChars[j] != c) {
                    geneChars[j] = c;
                }
 
                String mutatedGene = new String(geneChars);
 
                // ถ้าพบยีนเป้าหมาย
                if (mutatedGene.equals(endGene)) {
                    System.out.println(mutationCount);
                    return;
                }
 
                // ตรวจสอบว่ายีนที่กลายพันธุ์อยู่ใน bank หรือไม่
                for (int k = 0; k < bankAmount; k++) {
                    if (!visited[k] && geneBank[k].equals(mutatedGene)) {
                        queue[rear++] = mutatedGene;
                        visited[k] = true;
                    }
                }
 
                // คืนค่าเดิม
                geneChars[j] = currentGene.charAt(j);
            }
        }
    }
}

แผนภาพการทำงาน

ตัวอย่างการทำงาน

กรณี 1: มีเส้นทางการกลายพันธุ์

startGene: "AAAAACCC"
endGene:   "AAAAATCC"
geneBank:  ["AAAAATCC"]
ผลลัพธ์: 1 (เปลี่ยน C เป็น T หนึ่งครั้ง)

กรณี 2: ไม่มีเส้นทางการกลายพันธุ์

startGene: "AAAAAACC"
endGene:   "CCCCCCCC"
geneBank:  ["CCCCCCCC"]
ผลลัพธ์: -1 (ไม่สามารถกลายพันธุ์ได้)
ปรับปรุงล่าสุด