热门标签 | 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

 


推荐阅读
  • 本文介绍了UUID(通用唯一标识符)的概念及其在JavaScript中生成Java兼容UUID的代码实现与优化技巧。UUID是一个128位的唯一标识符,广泛应用于分布式系统中以确保唯一性。文章详细探讨了如何利用JavaScript生成符合Java标准的UUID,并提供了多种优化方法,以提高生成效率和兼容性。 ... [详细]
  • 在Java编程中,若需实现两个整数(例如2和3)相除并保留两位小数的结果,可以通过精确计算方法来达到预期效果。具体而言,可以利用BigDecimal类进行高精度运算,确保2除以3的结果准确显示为0.66。此外,还可以通过格式化输出来控制小数位数,确保最终结果符合要求。 ... [详细]
  • 本文深入解析了Java面向对象编程的核心概念及其应用,重点探讨了面向对象的三大特性:封装、继承和多态。封装确保了数据的安全性和代码的可维护性;继承支持代码的重用和扩展;多态则增强了程序的灵活性和可扩展性。通过具体示例,文章详细阐述了这些特性在实际开发中的应用和优势。 ... [详细]
  • 本文介绍了如何在iOS平台上使用GLSL着色器将YV12格式的视频帧数据转换为RGB格式,并展示了转换后的图像效果。通过详细的技术实现步骤和代码示例,读者可以轻松掌握这一过程,适用于需要进行视频处理的应用开发。 ... [详细]
  • 深入理解 Java 控制结构的全面指南 ... [详细]
  • 在Eclipse中批量转换Java源代码文件的编码格式从GBK到UTF-8是一项常见的需求。通过编写简单的Java代码,可以高效地实现这一任务。该方法不仅适用于Java文件,还可以用于其他类型的文本文件编码转换。具体实现可以通过导入`java.io.File`类来操作文件系统,从而完成批量转换。此外,建议在转换过程中添加异常处理机制,以确保代码的健壮性和可靠性。 ... [详细]
  • 在Android应用开发中,实现与MySQL数据库的连接是一项重要的技术任务。本文详细介绍了Android连接MySQL数据库的操作流程和技术要点。首先,Android平台提供了SQLiteOpenHelper类作为数据库辅助工具,用于创建或打开数据库。开发者可以通过继承并扩展该类,实现对数据库的初始化和版本管理。此外,文章还探讨了使用第三方库如Retrofit或Volley进行网络请求,以及如何通过JSON格式交换数据,确保与MySQL服务器的高效通信。 ... [详细]
  • 本指南从零开始介绍Scala编程语言的基础知识,重点讲解了Scala解释器REPL(读取-求值-打印-循环)的使用方法。REPL是Scala开发中的重要工具,能够帮助初学者快速理解和实践Scala的基本语法和特性。通过详细的示例和练习,读者将能够熟练掌握Scala的基础概念和编程技巧。 ... [详细]
  • 在Java编程中,`AbstractClassTest.java` 文件详细解析了抽象类的使用方法。该文件通过导入 `java.util.*` 包中的 `Date` 和 `GregorianCalendar` 类,展示了如何在主方法 `main` 中实例化和操作抽象类。此外,还介绍了抽象类的基本概念及其在实际开发中的应用场景,帮助开发者更好地理解和运用抽象类的特性。 ... [详细]
  • Android中将独立SO库封装进JAR包并实现SO库的加载与调用
    在Android开发中,将独立的SO库封装进JAR包并实现其加载与调用是一个常见的需求。本文详细介绍了如何将SO库嵌入到JAR包中,并确保在外部应用调用该JAR包时能够正确加载和使用这些SO库。通过这种方式,开发者可以更方便地管理和分发包含原生代码的库文件,提高开发效率和代码复用性。文章还探讨了常见的问题及其解决方案,帮助开发者避免在实际应用中遇到的坑。 ... [详细]
  • 手指触控|Android电容屏幕驱动调试指南
    手指触控|Android电容屏幕驱动调试指南 ... [详细]
  • 本文总结了JavaScript的核心知识点和实用技巧,涵盖了变量声明、DOM操作、事件处理等重要方面。例如,通过`event.srcElement`获取触发事件的元素,并使用`alert`显示其HTML结构;利用`innerText`和`innerHTML`属性分别设置和获取文本内容及HTML内容。此外,还介绍了如何在表单中动态生成和操作``元素,以便更好地处理用户输入。这些技巧对于提升前端开发效率和代码质量具有重要意义。 ... [详细]
  • AIX编程挑战赛:AIX正方形问题的算法解析与Java代码实现
    在昨晚的阅读中,我注意到了CSDN博主西部阿呆-小草屋发表的一篇文章《AIX程序设计大赛——AIX正方形问题》。该文详细阐述了AIX正方形问题的背景,并提供了一种基于Java语言的解决方案。本文将深入解析这一算法的核心思想,并展示具体的Java代码实现,旨在为参赛者和编程爱好者提供有价值的参考。 ... [详细]
  • HBase Java API 进阶:过滤器详解与应用实例
    本文详细探讨了HBase 1.2.6版本中Java API的高级应用,重点介绍了过滤器的使用方法和实际案例。首先,文章对几种常见的HBase过滤器进行了概述,包括列前缀过滤器(ColumnPrefixFilter)和时间戳过滤器(TimestampsFilter)。此外,还详细讲解了分页过滤器(PageFilter)的实现原理及其在大数据查询中的应用场景。通过具体的代码示例,读者可以更好地理解和掌握这些过滤器的使用技巧,从而提高数据处理的效率和灵活性。 ... [详细]
  • 如何使用 net.sf.extjwnl.data.Word 类及其代码示例详解 ... [详细]
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社区 版权所有