首页 > ACM题库 > HDU-杭电 > HDU 2941-Motif Finding-待解决[解题报告]
2014
02-24

HDU 2941-Motif Finding-待解决[解题报告]

Motif Finding

问题描述 :

Cell differentiation and development are fundamentally controlled by gene regulation. Only a subset of genes in the genome is expressed in a cell at a given time under given conditions. Regulatory sites on DNA sequence normally correspond to shared conservative sequence patterns among the regulatory regions of correlated genes. We call these conserved sequence motifs. The actual regulatory DNA sites corresponding to a motif are called the instances of that motif.
Identifying motifs and corresponding instances are very important, so biologists can investigate the interactions between DNA and proteins, gene regulation, cell development and cell reaction.Given two equal-length strings, the Hamming Distance is the number of positions in which the corresponding characters are different. For example, the Hamming Distance between “ACTG” and “ATCG” is 2 because they differ at the 2nd and 3rd positions.

Your task is to find a motif for a few DNA sequences. Every DNA sequence consists of only A, C, G, T. If a substring of DNA sequence S has the same length with motif P and their Hamming Distance is not more than d, we say that S includes an instance of P. Given n DNA sequences with length of l. Among them, m sequences are “key sequences”. You need to find out the motif P whose length is w, so that every key sequence includes an instance of motif P. What’s more, the number of DNA sequences which include an instance of P should be as large as possible.

For example, n=7, m =7, l=40, w =8, d =2. The sequences are as follows (they are all key sequences):


The motif P is ATGCAACT.

输入:

The input contains several cases. The first line of each case contains three integers n (1 ≤ n ≤ 15), m (0 ≤ m ≤ n) and l (1 ≤ l ≤ 10,000). The second line contains two integers w (1 ≤ w ≤ 8) and d (0 ≤ d ≤ w). The third line contains m unique integers ranging from 0 to n-1, indicating the key sequences.Then followed by n lines, in which each line contains one sequence. The input is terminated by three zeros.

输出:

The input contains several cases. The first line of each case contains three integers n (1 ≤ n ≤ 15), m (0 ≤ m ≤ n) and l (1 ≤ l ≤ 10,000). The second line contains two integers w (1 ≤ w ≤ 8) and d (0 ≤ d ≤ w). The third line contains m unique integers ranging from 0 to n-1, indicating the key sequences.Then followed by n lines, in which each line contains one sequence. The input is terminated by three zeros.

样例输入:

3 2 4
3 1
0 2
ACTT
CGTG
CCCC
3 2 4
3 0
0 2
ACTT
CGTG
CCCC
0 0 0

样例输出:

CCT
No solution

  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了