使用贪心算法解决基因拼接（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;
    @Override
    public 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

运行结果如下：

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