热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

华为OJ平台——DNA序列

题目描述:一个DNA序列由ACGT四个字母的排列组合组成。G和C的比例(定义为GC-Ratio)是序列中G和C两个字母的总的出现次数除以总的字母数目(也就是序列长度)。在基因工程中,这个

题目描述:

一个DNA序列由A/C/G/T四个字母的排列组合组成。G和C的比例(定义为GC-Ratio)是序列中G和C两个字母的总的出现次数除以总的字母数目(也就是序列长度)。在基因工程中,这个比例非常重要。因为高的GC-Ratio可能是基因的起始点。
给定一个很长的DNA序列,以及要求的最小子序列长度,研究人员经常会需要在其中找出GC-Ratio最高的子序列。
输入
  输入一个string型基因序列,和int型子串的长度
输出
  找出GC比例最高的字串
样例输入
  AACTGTGCACGACCTGA 5
样例输出
   GCACG

思路:

最常见和最易想到的方法是直接截取一个长度不小于minLen的子串,然后判断其中的GC-Ratio;确定这个子串是否是GC-Ratio最大的,但是此方法复杂度太高,每次截取子串后又要对子串进行遍历统计。

所以,我提出了下面的方法,对于一个确定的起点,对最长的子串进行一次遍历就可以确定以此为起点的相应的最高的GC-Ratio的子串,这样复杂度有所降低

 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 }
Code

 


推荐阅读
author-avatar
手机用户2602890793
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有