基因相关性

题目描述

比对两条长度相同（长度不大于 $500$ ）的 DNA 序列：相同位置的碱基构成一个碱基对，两碱基相同则为相同碱基对；相同碱基对比例大于等于给定阈值时判定相关。输入第一行为阈值，随后两行各为一条 DNA 序列。输出一行，相关输出 yes，否则输出 no。样例输入 0.85 / ATCGCCGTAAGTAACGGTTTTAAATAGGCC / ATCGCCGGAAGTAACGGTCTTAAATAGGCC，输出 yes。

思路

逐位比较两条序列，统计相同碱基对的个数 $k$ 。设序列长度为 $n$ ，判断 $k/n \geqslant x$ 是否成立即可，等于阈值也算相关。一遍线性扫描 $O(n)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 20:15
# update_at: 2026-10-04 09:35

import sys


def solve() -> None:
    # 阈值在输入最前，随后依次是两条等长 DNA 序列
    data = iter(sys.stdin.buffer.read().split())
    threshold = float(next(data))
    seq1, seq2 = next(data), next(data)

    length = len(seq1)
    same = sum(a == b for a, b in zip(seq1, seq2))  # 相同碱基对的个数

    print("yes" if same / length >= threshold else "no")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-29 20:15
 * update_at: 2026-10-05 02:53
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 505;
char seq1[maxn]; // 第一条 DNA 序列
char seq2[maxn]; // 第二条 DNA 序列
double threshold; // 判定相关的阈值

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> threshold >> seq1 >> seq2;

    ll length = strlen(seq1);
    ll same = 0; // 相同碱基对的个数
    for (ll i = 0; i < length; i++) {
        if (seq1[i] == seq2[i]) {
            same++;
        }
    }

    // 相同碱基对比例与阈值比较，注意含等号
    double ratio = 1.0 * same / length;
    if (ratio >= threshold) {
        cout << "yes" << "\n";
    } else {
        cout << "no" << "\n";
    }

    return 0;
}

目录

题目描述

思路

参考代码