首页 > 试题广场 >

DNA序列

[编程题]DNA序列

热度指数：133892 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

一个 DNA 序列由 A/C/G/T 四个字母的排列组合组成。 G 和 C 的比例（定义为 GC-Ratio ）是序列中 G 和 C 两个字母的总的出现次数除以总的字母数目（也就是序列长度）。在基因工程中，这个比例非常重要。因为高的 GC-Ratio 可能是基因的起始点。

给定一个很长的 DNA 序列，以及限定的子串长度 N ，请帮助研究人员在给出的 DNA 序列中从左往右找出 GC-Ratio 最高且长度为 N 的第一个子串。

DNA序列为 ACGT 的子串有: ACG , CG , CGT 等等，但是没有 AGT ， CT 等等

数据范围：字符串长度满足 $1 \le n \le 1000 \$ ，输入的字符串只包含 A/C/G/T 字母

输入描述:

输入一个string型基因序列，和int型子串的长度

输出描述:

找出GC比例最高的子串,如果有多个则输出第一个的子串

示例1

输入

ACGT
2

输出

CG

说明

ACGT长度为2的子串有AC,CG,GT3个，其中AC和GT2个的GC-Ratio都为0.5，CG为1，故输出CG

示例2

输入

AACTGTGCACGACCTGA
5

输出

GCACG

说明

虽然CGACC的GC-Ratio也是最高，但它是从左往右找到的GC-Ratio最高的第2个子串，所以只能输出GCACG。

算法知识视频讲解

JSON495

发表于 2021-12-02 11:45:40

正则很重要 import java.util.*; public class Main{ public static void main(String [] args){ Scanner sc = new Scanner(System.in); while(s 展开全文

牛客484960258号

发表于 2021-12-28 16:55:19

while True: try: DNA = input() length = int(input()) max_counts = 0 max_DNA = [] for i in range(len(DNA)-l 展开全文

牛客618200904号

发表于 2020-09-20 22:48:08

首先，大家得理解题意，子串长度是固定的，因此要使子串中GC-Ratio最大，只需子串中的GC数量达到最大即可，不需要去计算比例。思路：使用双指针维护一个长度固定的子串，逐步向后遍历，类似于滑动窗口，每加入一个字符，更新子串GC的数量，并记录位置，遍历完毕整个序列即可得到最大GC比例的子串出现的位置。展开全文

牛客400264395号

发表于 2022-01-06 15:55:08

a = input().strip() n = int(input()) l = [] m = [] for i in range(len(a)): s = a[i:i+n].count('G') + a[i:i+n].count('C') l.append(a[i:i+n]) 展开全文

摸鱼学大师

发表于 2021-10-27 21:29:19

题目的主要信息：输入的字符串中只有ACGT四种字符限定长度为nnn的子串，求其中CG比例最高的第一个子串解读：长度限定的情况下，要找比例越高即找出现次数越多方法一：暴力解法具体做法：我们可以遍历字符串每个位置作为起始，然后遍历以这个字符作为起始的长为nnn的子串，分别统计子串中CG 展开全文

godhands

发表于 2021-11-10 23:14:27

描述题目描述我们将繁琐的题意化简，其实本质上就是给了我们一个字符串里面只会含有，CGAT这四种字符，然后在给我们一个n 代表我们要寻找的子串的长度，我们要找到第一个CG比例最多的子串，然后输出这个子串样例解释 ACGT 2 首先给了我们这么一个字符串 ACGT，然后要我们找到一个长度为 2 展开全文