DNA序列

"""
DNA序列
DNA序列由一系列核苷酸组成，分别是为A(腺嘌呤)、T(胸腺嘧啶)、C(胞嘧啶)、G(鸟粪嘌呤)
例如，AATCCGCTAG是一个DNA序列。
在研究DNA时，识别DNA中的重复序列非常有用，
给定一个表示DNA序列的字符串，
返回所有在字符串中出现不止一次的长度为10的序列(子字符串)
"""
from collections import defaultdict

def dna_analysis(s):
    """
    分析DNA序列，寻找重复的k-mer子串。

    :param s: 输入的DNA序列字符串
    :return: 所有重复出现两次的长度为k的子串列表，其中k为预定义的标准长度
    """
    # 定义标准k-mer长度
    standard = 10
    # 构建字符到整数的映射，用于将字符转换为二进制表示
    ht_char = {"A":0,"C":1,"G":2,"T":3}
    # 初始化结果列表，用于存储找到的重复k-mer子串
    result = []
    # 获取输入序列的长度
    length = len(s)
    # 如果输入序列长度小于等于标准k-mer长度，则直接返回空结果
    if length <= standard:
        return result
    # 初始化用于存储当前k-mer的二进制表示的变量
    x = 0
    # 构建第一个k-mer的二进制表示
    for char in s[:standard -1]:
        x = (x << 2) | ht_char[char]
    # 使用哈希表记录每个k-mer出现的次数
    ht_count = defaultdict(int)
    # 遍历输入序列，寻找重复的k-mer
    for i in range(length - standard + 1):
        # 更新当前k-mer的二进制表示，将新的字符加入，旧的字符移除
        x = ((x << 2) | ht_char[s[i + standard - 1]]) & ((1 << (standard *2)) -1)
        # 记录当前k-mer出现的次数
        ht_count[x] += 1
        # 如果当前k-mer出现次数达到2次，则将其添加到结果列表
        if ht_count[x] ==2:
            result.append(s[i:i+standard])
    # 返回结果列表
    return result
print(dna_analysis("AAAGTCTGACAAAGTCTGACACAAAGTCTGTT"))