大型DNA字符串基因查找算法错误排查求助

我正在编写一个从大型DNA字符串中查找基因的程序，该程序在小型DNA输入字符串上输出正确，但测试大型示例DNA字符串时输出错误。以下是我的Java代码及测试输出，请求协助排查问题：

原Java代码 #

public class part1 
{
    // 查找终止密码子
    public int findStopCodon(String dna, int startIndex, String stopCodon)
    {
        int stopIndex = dna.indexOf(stopCodon, startIndex);
        if (stopIndex != -1)
        {
            if (dna.substring(startIndex, stopIndex + 3).length() % 3 == 0)
            {
                return stopIndex;
            }
        }
        return dna.length();
    }

    // 查找基因
    public String findGene(String dna, int startIndex)
    {
        if ( startIndex != -1)
        {
            int taaIndex = findStopCodon(dna, startIndex, "TAA");
            int tgaIndex = findStopCodon(dna, startIndex, "TGA");
            int tagIndex = findStopCodon(dna, startIndex, "TAG");

            int temp = Math.min(taaIndex, tgaIndex);
            int minIndex = Math.min(temp, tagIndex);
            if (minIndex <= dna.length() - 3)
            {
                return dna.substring(startIndex, minIndex + 3);
            }
        }
        return "";
    }

    // 将所有基因存入StorageResource
    public StorageResource allGenes(String dna)
    {
        StorageResource geneList = new StorageResource();
        int prevIndex = 0;
        while (prevIndex <= dna.length())
        {
            int startIndex = dna.indexOf("ATG", prevIndex);
            if (startIndex == -1)
            {
                return geneList;
            }
            String gene = findGene(dna, startIndex);
            if (gene.isEmpty() != true)
            {
                geneList.add(gene);
            }
            prevIndex = startIndex + gene.length() + 1;
        }
        return geneList;
    }
}

测试输出 #

this many genes: 106

number of length > 60: 31

number of cgRatio > 0.35: 54

longest: 282

CTG appears: 224 times

问题分析与修正方案 #

1. 终止密码子查找逻辑错误（核心问题） #

findStopCodon方法仅查找第一个出现的终止密码子，若其与起始密码子（ATG）的间隔不是3的倍数，就直接返回dna.length()，放弃后续可能符合条件的终止密码子。这会导致大型DNA字符串中大量有效基因被遗漏。

修正代码：

public int findStopCodon(String dna, int startIndex, String stopCodon) {
    int currentIndex = dna.indexOf(stopCodon, startIndex);
    // 循环查找，直到找到符合条件的终止密码子或遍历结束
    while (currentIndex != -1) {
        // 直接用数值计算判断间隔是否为3的倍数，避免创建冗余子字符串
        if ((currentIndex - startIndex) % 3 == 0) {
            return currentIndex;
        }
        // 从当前终止密码子的下一个位置继续查找
        currentIndex = dna.indexOf(stopCodon, currentIndex + 3);
    }
    return dna.length();
}

2. 基因遍历的起始位置更新错误 #

allGenes方法中，找到有效基因后prevIndex被设置为startIndex + gene.length() + 1，多添加的+1会导致跳过下一个可能起始于基因结束位置的ATG，遗漏潜在基因。

修正代码：

// 去掉+1，直接从当前基因的结束位置开始下一次查找
prevIndex = startIndex + gene.length();

3. 冗余的字符串操作优化 #

原findStopCodon中用dna.substring(...).length()判断间隔是否为3的倍数，会创建不必要的子字符串，影响大型字符串的处理性能。修正后直接用数值计算(currentIndex - startIndex) % 3 == 0替代，逻辑等价且更高效。

4. 基因判断逻辑简化 #

findGene中判断minIndex <= dna.length() - 3可简化为minIndex != dna.length()，因为findStopCodon返回dna.length()时代表未找到有效终止密码子，其余返回值必然是合法的终止密码子起始位置（即满足<= dna.length() -3）。

简化后的findGene片段：

int minIndex = Math.min(Math.min(taaIndex, tgaIndex), tagIndex);
if (minIndex != dna.length()) {
    return dna.substring(startIndex, minIndex + 3);
}

内容的提问来源于stack exchange，提问作者isaiah paget