1 import java.util.Scanner;
2
3 /**
4 * 一个DNA序列由A/C/G/T四个字母的排列组合组成。G和C的比例(定义为GC-Ratio)是
5 * 序列中G和C两个字母的总的出现次数除以总的字母数目(也就是序列长度)。在基因工程
6 * 中,这个比例非常重要。因为高的GC-Ratio可能是基因的起始点。
7 * 给定一个很长的DNA序列,以及要求的最小子序列长度,研究人员经常会需要在其中找
8 * 出GC-Ratio最高的子序列
9 *
10 * 输入
11 * 输入一个string型基因序列,和int型子串的长度
12 * 输出
13 * 找出GC比例最高的字串
14 * 样例输入 AACTGTGCACGACCTGA 5
15 * 样例输出 GCACG
16 *
17 */
18 public class DNASeq {
19
20 public static void main(String[] args) {
21 // 输入读取参数
22 Scanner cin = new Scanner(System.in);
23 String seq = cin.next();
24 int minLen = cin.nextInt() ;
25 cin.close();
26
27 System.out.println(findOpticalSubseq(seq,minLen));
28
29 }
30
31 /**
32 * 输入字符串和最小子串长度,返回GC-Ratio最高的子串
33 * @param seq
34 * @param minLen
35 * @return
36 */
37 private static String findOpticalSubseq(String seq, int minLen) {
38 String res ;
39 //记录GC-Ratio最高的子串在字符串seq中的起点和终点
40 int [] index = new int[2] ;
41 float maxRatio = 0.0f ;
42 int count ;
43
44 /*
45 * 最常见和最易想到的方法是直接截取一个长度不小于minLen的子串,然后判断其中的GC-Ratio;
46 * 确定这个子串是否是GC-Ratio最大的,但是此方法复杂度太高,每次截取子串后又要对子串进行遍历统计
47 * 所以,我提出了下面的方法,对于一个确定的起点,一次对最长的子串进行一次遍历就可以确定相应的
48 * 最高的GC-Ratio的子串的起点和终点,复杂度有所降低
49 */
50 for(int i = 0 ; i <(seq.length() - minLen) ; i++){
51 count = 0 ;
52 for(int j = i ; j ){
53 if(seq.charAt(j) == 'G' || seq.charAt(j) == 'C'){
54 count++ ;
55 }
56 //满足子串长度要求以及GC-Ratio更高的时候更新GC-Ratio和起点和终点的值
57 if((j-i+1) >= minLen && count/(j-i+1.0f) > maxRatio){
58 maxRatio = count/(j-i+1.0f) ;
59 index[0] = i ;
60 index[1] = j ;
61 }
62 }
63 }
64
65 //根据起点和终点的位置确定返回的子串
66 if(index[1] == (seq.length()-1)){
67 res = seq.substring(index[0]) ;
68 }else{
69 res = seq.substring(index[0], index[1]+1) ;
70 }
71
72 return res ;
73 }
74
75 }