本文主要是介绍Rosalind Java|Speeding Up Motif Finding,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Rosalind编程问题之计算错误矩阵(failure array)输出前后缀检索匹配。
Speeding Up Motif Finding
Problem:
A prefix of a length n string s is a substring s[1:j]; a suffix of s is a substring s[k:n].
The failure array of s is an array P of length n for which P[k] is the length of the longest substring s[j:k] that is equal to some prefix s[1:k−j+1], where j cannot equal 1 (otherwise, P[k] would always equal k). By convention, P[1]=0.
Given: A DNA string s (of length at most 100 kbp) in FASTA format.
Sample input:
Rosalind_87
CAGCATGGTATCACAGCAGAG
Return: The failure array of s.
Sample output:
0 0 0 1 2 0 0 0 0 0 0 1 2 1 2 3 4 5 3 0 0
本题定义了一个概念叫做错误矩阵(failure array)。错误矩阵的元素数量与题目给出的一段字符序列长度是相等的。从头遍历一段字符序列s,当遍历到第k个字符时,前k个字符会组成一段子序列s[1:k]。此时,子序列前j个字符(子序列前缀)和后j个字符(子序列后缀)如果相等,那么j就是当下的最长匹配数。当j从1到k-1逐次递增时,产生的子序列前缀和后缀会逐渐延长,并经历数次比对,若前缀等于后缀,则此时的j会更新上一个j,成为新的最长匹配数。当j遍历完时,最大的j会被记录在错误矩阵第k个位置,即p[k]。以此类推得到错误矩阵所有的元素。
解题思路如下:
1.手动输入读取DNA序列。
2.设定字符i以截取序列。
3.设定字符j以截取子序列的前缀和后缀。
4.若前缀=后缀,则记录当下的j,依次迭代。
代码如下:
public class AAAA_Speeding_Up_Motif_Finding {public static void main(String[] args) {//1.输入DNA序列Scanner sc = new Scanner(System.in);System.out.println("请输入DNA序列:");String DNA = sc.nextLine();for (int i = 1; i <= DNA.length(); i++) {//第i个字符代表此时的错误矩阵数值,n个字符就有n个数值输出int longest = 0;for (int j = 0; j < i; j++) {//j表示前缀后移碱基数和后缀前移碱基数,i和j不能相等,否则最长序列一定是全长String prefs = DNA.substring(0, j);String suffs = DNA.substring(i - j, i);if (prefs.equals(suffs)) {longest = j;}}System.out.print(longest + " ");}}
}
这篇关于Rosalind Java|Speeding Up Motif Finding的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!