病毒溯源(25分)
发布时间
阅读量:
阅读量
某些病毒具有易变性的特点。一些特定的病毒可能会经历突变过程而产生不同类型的子代毒株。这些产生的子代毒株在进一步复制过程中也可能发生突变而导致新的变异类型。
现给定一些病毒之间的变异关系,要求你找出其中最长的一条变异链。
在本研究中假设这些特定的变异事件都源于单一祖先病毒的独立突变,并暂且忽略复杂的基因重组可能导致的多样性增加 —— 即认为所有被研究的病毒个体都源自单一祖先病毒的独立突变,并未发生循环或连锁突变。
输入格式:
输入在第一行中指定一个正整数 N(\leq 10^4),表示病毒种类的数量。随后我们将所有病毒依次编号为 0, 1, \ldots, N-1。
随后 N 行,每行按以下格式描述一种病毒的变异情况:
其中 k 代表了该病毒所有可能产生的变异毒株的数量;具体记录了每一种变异毒株的具体编号信息;每个第 i 行都明确标注了对应病毒个体的具体编号(假设总共有 N 个样本);确保整个数据集只有一个原始来源样本作为基准进行分析。
输出格式:
首先输出从源头开始最长变异链的长度。
在第2行输出从源头出发最长的一条变异通路,在编排上确保编号之间用一个空格分隔,并且行的前后不得留有额外空白。若最长通路不唯一,则输出最短编号序列
我们称序列为A的小于序列为B的条件是存在一个位置k(1到n之间),使得在所有i小于k的位置上ai
全部评论 (0)
还没有任何评论哟~
