Java贪心算法解决基因拼接(Gene Assembly)问题

使用贪心算法解决基因拼接(Gene Assembly)问题:

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


实验内容:

一、实验目的

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

二、实验内容

【问题描述】

   随着大量的基因组DNA序列数据被获得, 它对于了解基因越来越重要(基因组DNA的一部分, 是负责蛋白质合成的) 。众所周知, 在基因组序列中, 由于存在垃圾的DNA中断基因的编码区,真核生物(相对于原核生物)的基因链更加复杂。也就是说,一个基因被分成几个编码片段(称为外显子)。虽然在蛋白质的合成过程中,外显子的顺序是固定的,但是外显子的数量和长度可以是任意的。

  大多数基因识别算法分为两步:第一步,寻找可能的外显子;第二步,通过寻找一条拥有尽可能多的外显子的基因链,尽可能大地拼接一个基因。这条链必须遵循外显子出现在基因组序列中的顺序。外显子i在外显子j的前面的条件是i的末尾必须在j开头的前面。

  本题的目标是,给定一组可能的外显子,找出一条拥有尽可能多的外显子链,拼接成一个基因。

【输入】

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

Java贪心算法解决基因拼接(Gene Assembly)问题

【输出】

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

Java贪心算法解决基因拼接(Gene Assembly)问题

分析与思路:

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


代码如下:

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

运行结果如下:

Java贪心算法解决基因拼接(Gene Assembly)问题

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

Java贪心算法解决基因拼接(Gene Assembly)问题

上一篇:浅析Asp.Net Core框架IConfiguration配置


下一篇:【UCSC Genome Browser】Genes and Gene Predictions - GENCODE