算法设计Project:寻找结构变异

更新记录

2016-6-24:
添加一组新的数据

2016-5-30:
添加五组新的数据
以及奇怪的评测系统,如果出现故障请联系我。
P.S. 期末提交代码时可能会查重,所以建议同学们不要互相交流代码(毕竟这个PJ也不难嘛...)

2016-4-10:
增加一个计算输出得分的工具
添加三组新的数据

2016-4-9:
重要:更新关于结构变异——倒位的说明
添加各种结构变异的样例

背景

DNA序列

DNA序列为字符集为Σ={A, C, G, T, N} 的字符串。

其中N表示未知,可能为A, C, G, T中任一个。(也可以理解为通配符)

测序技术

常规测序

对于普通的测序,我们先通过PCR技术将DNA复制若干份。再将它们随机切割为长度接近的小段,分别进行测序。
这样我们将得到大量互相交叠的小段,可通过重叠部分将其拼接起来得到完整的DNA序列。

简而言之,测序后得到的数据将是大量长度接近,均匀分布的原字符串的子串。

序列的方向

方向 说明 示例
原始方向 一般任意选择一条链为序列的原始方向 ACAGT
相反方向 与原始方向方向相反 TGACA
互补方向 DNA中另一条链上的序列方向,即原串按照A-T,C-G转换后得到的序列 TGTCA
互补相反方向 既互补又相反 ACTGT

Paired end技术

在测序时,若复制次数过少即子串数量过少,则交叠部分不足,可能无法拼接出完整的序列,而增加复制次数则会成倍增加成本。

因此提出了paired end技术。即先将原串切割为长度接近的较长片段,再从长段两侧分别测序之前小段的长度。
这样我们将会得知某一对字串之间的大致距离,方便拼接出完整的序列。
由于paired-end测序时从两条链的两端向中间进行测序,因此会得到一个原始方向的子串和一个互补相反方向的子串

测序错误

由于技术原因,DNA测序得到的子串会有一定几率错误(几率小于每个字符1%)
测序错误体现为

  1. 替换:某一位置字符替换为其他字符。

  2. 插入:两字符间插入一字符。

  3. 删除:某字符未被测出而缺失。

注意:

由于测序错误是发生在单个字符上且几率很小,所以发生连续一长段全是测序错误的可能性近乎为0。

你只需要汇报结构变异,无需汇报测序错误。

染色体结构变异

染色体结构变异(SV)是染色体变异的一种,通常长度在200到1000之间。
在自然条件或人为因素的影响下,染色体发生的结构变异主要有3种:

  1. 缺失

    假设原串s=s1+s2+s3

    则发生缺失变异后的字符串s'=s1+s3

    例如:
    参考串:ACGTAGC 第3-5字符发生缺失
    变异串:ACGC

  1. 重复

    假设原串s=s1+s2+s3

    则发生重复变异后的字符串s'=s1+s2+s2+s3

    例如:
    参考串:ACGTAGC 第3-5字符发生重复
    变异串:ACGTAGTAGC

  1. 倒位

    假设原串s=s1+s2+s3

    则发生重复变异后的字符串s'=s1+s2'+s3

    其中s2'为s2的互补相反字符串

    例如:
    参考串:ACGTAGC 第3-5字符发生倒位
    变异串:ACTACGC

问题

给出一参考DNA序列和比较DNA序列的测序结果,及测序参数。 求比较序列相对参考DNA序列发生的缺失、重复、倒位结构变异。

注意:这里比较序列中可能包含
  1. 和参考DNA序列相同的部分
  2. 参考DNA序列经由结构变异产生的部分
  3. 与参考序列无关的部分(模拟数据不包含)
注意:结构变异发生在序列上,即参考序列经过结构变异产生比较序列。 而你得到的不是比较序列,是比较序列的测序结果(即若干子串)。

数据格式

输入

1. "seq.txt"

文件包含一行:参考DNA序列(长字符串)

2. "1.txt" "2.txt"

文件包含比较序列的测序结果

文件中每行代表一个子串。

"1.txt" "2.txt"相同行数的子串成对。(paired-end)

注意:这里成对的子串一定有一个是原始方向(和参考序列相同),一个是互补相反方向。
不保证一定是原始方向在"1.txt"中,互补相反方向在"2.txt"中。
保证"1.txt"与"2.txt"行数相同

3. "param.json"

包含测序参数,及SV信息的json文件

其中包含:
  • name:测试数据名称

  • sv_min_length:结构变异长度最小值

  • sv_max_length:结构变异长度最大值

  • read_length:测序结果中子串平均长度

  • pair_distance:成对字串之间平均距离

    这里距离指成对子串两段间距离。即:{距离} = {前面子串(正向)长度} + {中间距离} + {后面子串(互补相反)长度}

  • standard_deviation:成对字串间距离的标准差。

  • coverage:测序时比较序列的复制次数。

    即:{复制次数} ≈ {子串数量} * {子串平均长度} / {比较序列长度(与参考序列长度接近)}

  • error_rate:测序错误概率

输出

每行代表一个推测可能的结构变异。

每行包括空白符分割的:

  1. 一个字符串,代表结构变异的种类

    DEL--缺失,DUP--复制,INV--倒位

  2. 一个数字,代表结构变异在参考串中的起始位置

  3. 一个数字,代表结构变异在参考串中的结束位置

对于缺失:
参考串:s = s1 + s2 + s3
比较串:s = s1 + s3
回报s2在参考串中的位置。
对于复制:
参考串:s = s1 + s2 + s3
比较串:s = s1 + s2 + s2 + s3
回报s2在参考串中的位置。
对于倒位:
参考串:s = s1 + s2 + s3
比较串:s = s1 + s2'+ s3
回报s2在参考串中的位置。

注意:

  1. 对于某一回报的结构变异,只要与答案相比种类相同,覆盖长度大于总长度90%即算正确。
  2. 允许答案中结构变异数量3倍以内的多报,超过答案数量3倍的输出无效

数据规模

模拟数据

对于所有模拟数据,保证比较DNA序列直接经由参考DNA序列发生若干次结构变异产生。即比较序列不包含和参考序列无关的部分。

保证结构变异不相互重叠。

目前公布的类型:

类型序号 参考序列长度 测序错误概率 复制次数
A <=10000 0% 500
A2 <=10000 0.1% 500
B <=10000 0% 30
B2 <=10000 0.1% 30
C <=2000000 0 15
C2 <=2000000 0.1% 15
C3 <=2000000 0.1% 5

真实数据

Coming soon...

评判与提交

评判标准

测试分数主要取决于覆盖率,即正确回报占所有正确结构变异的比例。

其次考虑准确度,即正确回报占回报总数量的比例。

提交方式

可选择提交程序,或提交输出文件。

提交程序的测试环境:16核CPU,32G内存,Linux操作系统

提交的程序可使用多线程运行,时间限制将参考提交的程序及标程在对应数据上的运行时间决定。

测试数据下载

数据名称 数据类型 序列长度 错误概率 复制次数 输入文件 答案
Alpha 模拟数据A <=10000 0% 500 下载 下载
Alt 模拟数据A2 <=10000 0.1% 500 下载 下载
Beta 模拟数据B <=10000 0% 30 下载 下载
Backspace 模拟数据B2 <=10000 0.1% 30 下载 下载
cama 模拟数据C <=2000000 0 15 下载 下载
capslock 模拟数据C2 <=2000000 0.1% 15 下载 下载
alice 模拟数据A2 <=10000 0.1% 500 下载 提交答案
bob 模拟数据B2 <=10000 0.1% 30 下载 提交答案
camelia 模拟数据C2 <=2000000 0.1% 15 下载 提交答案
counterattack 模拟数据C3 <=2000000 0.1% 5 下载 提交答案

实用工具下载

工具名称 依赖 功能 下载
judge.py python3 根据输入的结果和答案进行测试,返回分数。分数中Sensitivity最为重要。 下载

参考文献

Rausch, Tobias, et al. "DELLY: structural variant discovery by integrated paired-end and split-read analysis." Bioinformatics 28.18 (2012): i333-i339.

联系我们

如果你对题目有疑问,或者评测系统出了故障,欢迎联系:

黄剑铮 14307130264@fudan.edu.cn