Java贪心算法解决基因拼接（Gene Assembly）问题_综合

使用贪心算法解决基因拼接（Gene Assembly）问题：

贪心算法一般按如下步骤进行：
①建立数学模型来描述问题。
②把求解的问题分成若干个子问题。
③对每个子问题求解，得到子问题的局部最优解。
④把子问题的解局部最优解合成原来解问题的一个解

实验内容：

一、实验目的

   练习使用贪心算法解决实际问题（使用Java语言实现）。

二、实验内容

【问题描述】

   随着大量的基因组DNA序列数据被获得， 它对于了解基因越来越重要(基因组DNA的一部分， 是负责蛋白质合成的) 。众所周知， 在基因组序列中， 由于存在垃圾的DNA中断基因的编码区，真核生物(相对于原核生物)的基因链更加复杂。也就是说，一个基因被分成几个编码片段(称为外显子)。虽然在蛋白质的合成过程中，外显子的顺序是固定的，但是外显子的数量和长度可以是任意的。大多数基因识别算法分为两步：第一步，寻找可能的外显子；第二步，通过寻找一条拥有尽可能多的外显子的基因链，尽可能大地拼接一个基因。这条链必须遵循外显子出现在基因组序列中的顺序。外显子i在外显子j的前面的条件是i的末尾必须在j开头的前面。本题的目标是，给定一组可能的外显子，找出一条拥有尽可能多的外显子链，拼接成一个基因。

【输入】

   给出几组输入实例。每个实例的开头是基因组序列中可能的外显子数n(0<n<1000)。接着的n行，每行是一对整数，表示外显子在基因组序列中的起始和结束位置。假设基因组序列最长为50000。当一行是0时，表示输入结束。

在这里插入图片描述

【输出】

   对于每个实例，找出最可能多的外显子链，输出链中的外显子，并占一行。假如有多条链，外显子数相同，那么，可以输出其中的任意一条。

在这里插入图片描述

分析与思路：

该题的解决方案类似于课上老师所讲的会议安排问题，因此，在原有代码基础上稍作修改。
采用的贪心选择策略：
对结束时间，进行升序排序。优先选择最先结束的外显子，这样就可以选择最多的外显子。

代码如下：

package Gene;public class Gene implements Comparable<Gene> {
    public int begin;public int end;public int number;@Overridepublic int compareTo(Gene o) {
    if(end==o.end){
    return o.begin-begin;}return end-o.end;}
}

package GeneAssembly;
import Gene.Gene;import java.util.Arrays;
import java.util.Scanner;public class GeneAssembly {
    int amount;Gene[] genes = new Gene[1000];public void init() {
    Scanner scanner = new Scanner(System.in);System.out.print("请输入外显子总数：");amount = scanner.nextInt();for (int i = 0; i < amount; i++) {
    Gene temp = new Gene();temp.number = i + 1;System.out.print("外显子" + temp.number + "的起始位：");temp.begin = scanner.nextInt();System.out.print("外显子"+temp.number + "的终止位：");temp.end = scanner.nextInt();System.out.println("***********************");genes[i] = temp;}}public void solve() {
    Arrays.sort(genes, 0, amount);System.out.println("拼接后的基因如下:");//选中了第一个外显子System.out.print(genes[0].number);//记录刚刚被选中外显子的终止位int last = genes[0].end;for (int i = 1; i < amount; i++) {
    if (genes[i].begin >= last) {
    last = genes[i].end;System.out.print(" "+genes[i].number);}}}
}

package TestMain;import GeneAssembly.GeneAssembly;import java.util.Scanner;public class TestMain {
    public static void main(String[] args){
    GeneAssembly gene =new GeneAssembly();int i=1;while (i==1){
    gene.init();gene.solve();System.out.println("是否还要输入外显子（1/0）");Scanner scanner=new Scanner(System.in);i=scanner.nextInt();}}
}

分三个包编写：Gene,GeneAssembly,TestMain

运行结果如下：

在这里插入图片描述

欢迎来我的公众号：玹之空间
更多精彩有趣，尽在其中！！
源文件可私信后台发送，也可在公众号自提！

在这里插入图片描述