编程介的小学生 2019-06-13 21:59 采纳率: 20.5%
浏览 184

字符串的差异的修改的比较,怎么利用C语言的程序的设计的形式的方式来解决的

Problem Description
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.

Input
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.

Output
For each case, output the motif P in one line. If the solution is not unique, then output the lexicographically smallest one. If there is no answer, you should output “No solution”.

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

Sample Output
CCT
No solution

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
    • ¥15 C#调用python代码(python带有库)
    • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
    • ¥15 活动选择题。最多可以参加几个项目?
    • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
    • ¥15 vs2019中数据导出问题
    • ¥20 云服务Linux系统TCP-MSS值修改?
    • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
    • ¥20 怎么在stm32门禁成品上增加查询记录功能
    • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面