码工们请听题

xiaxianyue
楼主 (未名空间)

你有100多份文件(并且将来还会不断有新文件传给你)。每份文件的内容大概在29903字母(目前的最大文件)到29840字母之间。每个字节只可能是A,T,C,G四个字母之
一,比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本,有各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被发掘出来后被copy成了电子版,现在要你分析哪个版本是原版。甚至有可能,有两三个原版。现在把信息量最大(29903字母)发掘时间比较靠前的文件(文件名Wuhan-HU1/
2019)作为原始版作为root of the tree。要求你设计一个算法,把其他文件根据相似度做一个树。

先看多少人有思路吧,之后我在细化加大难度。

最新回帖

TheMatrix
98 楼

Deterministic. 不错,谢谢。

【 在 kingcw (无语了) 的大作中提到: 】
: 找root node可以用leader election,这个算法自己定义
: 譬如选择weight为0的几个文件,也就是相同的文件最多的当leader,etc
: 这个问题没有讨论下去的必要了,浪费时间,楼主显然把这个版当成生物版了
: [在 TheMatrix (TheMatrix) 的大作中提到:]
: :我不是抬杠,minimum weight spanning tree,这个得到了。树杈多的是原版,这句
: 话能这么说吗?还是这是定论?
: :☆ 发自 iPhone 买买提 1.24.11

TheMatrix
97 楼

嗯,deterministic. 其合理性可能还需要讨论。

【 在 SLE (嗯,就这样定了。) 的大作中提到: 】
: 可以寻找使得树的深度最小的根。

kingcw
96 楼

找root node可以用leader election,这个算法自己定义

譬如选择weight为0的几个文件,也就是相同的文件最多的当leader,etc

这个问题没有讨论下去的必要了,浪费时间,楼主显然把这个版当成生物版了

[在 TheMatrix (TheMatrix) 的大作中提到:]
:我不是抬杠,minimum weight spanning tree,这个得到了。树杈多的是原版,这句
话能这么说吗?还是这是定论?
:☆ 发自 iPhone 买买提 1.24.11
S
SLE
95 楼

可以寻找使得树的深度最小的根。
【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 哦,树根定在已知的原始文件上,纲举目张,有道理。那如果不知道原始文件而要找原
: 始文件,那就不行了,对吧?

TheMatrix
94 楼

哦,树根定在已知的原始文件上,纲举目张,有道理。那如果不知道原始文件而要找原始文件,那就不行了,对吧?

【 在 SLE (嗯,就这样定了。) 的大作中提到: 】
: 计算每两个文件的距离,定义为从一个文件变成另一个文件需要的最少错误数。
: 然后找到这个图里的最小树。
: 再然后,如果你知道哪一个文件是原始文件,就可以得到所有文件的传承顺序。
: 29903

S
SLE
93 楼

计算每两个文件的距离,定义为从一个文件变成另一个文件需要的最少错误数。
然后找到这个图里的最小树。
再然后,如果你知道哪一个文件是原始文件,就可以得到所有文件的传承顺序。

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 你有100多份文件(并且将来还会不断有新文件传给你)。每份文件的内容大概在
29903
: 字母(目前的最大文件)到29840字母之间。每个字节只可能是A,T,C,G四个字母之
: 一,比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本,有
: 各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被发
: 掘出来后被copy成了电子版,现在要你分析哪个版本是原版。甚至有可能,有两三个原
: 版。现在把信息量最大(29903字母)发掘时间比较靠前的文件(文件名Wuhan-HU1/
: 2019)作为原始版作为root of the tree。要求你设计一个算法,把其他文件根据相似
: 度做一个树。
: 先看多少人有思路吧,之后我在细化加大难度。

TheMatrix
92 楼

标准正确答案?什么问题的标准正确答案啊?

【 在 SiegeCat () 的大作中提到: 】
: 第一页已经给出标准的正确答案了,其他人都在胡说八道
: 稍微解释一下 100 c 2 大概是5000个边。
: 整个图每一个顶点就是一个基因编码文件,每个边将两个文件相连。
: 通过某种模型判断出两个文件距离是多少,记录在这个边上,比方说简单的模型可以是
: 最小编辑距离(即一个文件变成另一个文件最小改变数)。
: 接着只要求出整个图的最小生成树即可,complexity是 O(E*N^2) + O(ELogV)
: E是文件对儿,也就是5000左右
: N是每个文件大小
: V是文件数量

TheMatrix
91 楼

我不是抬杠,minimum weight spanning tree,这个得到了。树杈多的是原版,这句话能这么说吗?还是这是定论?

【 在 kingcw (无语了) 的大作中提到: 】
: 他的问题是按照相似度建树啊,minimum edit distance就是相似度最近的,minimum
: weight树杈最多的就是原版
: 除非他重新定义相似度,give data meaning,不然string comparison不就是这个
: [在 TheMatrix (TheMatrix) 的大作中提到:]
: :算是能算出来,但是结果的物理意义不清楚啊。
: :☆ 发自 iPhone 买买提 1.24.11

lsunspot


缺如何决定先后的条件吧?就是AI也得先能supervised啊
xiaxianyue

这个确实很关键,也涉及到生物学细节。我们先简单假定Wuhan-HU1/2019就是最早期版本。其他细节等建树以后我们再fine tune。目前中国和GISAID的都是建好树了,但是
缺少fine tune,我现在的工作就是手工fine tune树的细节
【在 lsunspot (小手) 的大作中提到: 】
: 缺如何决定先后的条件吧?就是AI也得先能supervised啊

keyrock

你的题目也写的不对

而且不需要码公,只要有逻辑思维能力

病毒复制出错就是变异,出错点是随机的,出错就是独特序列,有这个独特序列的是同源

如果一个病毒有多个独特序列,每个都被其他一群病毒共有,这个就是祖宗
keyrock

这就是一棵树,每个分支就是变异的独特序列,树根有多个分支交汇
lsunspot

按手抄本来看的话,应该迭代越多偏离越大,以前叔会考虑定义偏离算法,现在就考虑train个model,让model自己发现

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 这个确实很关键,也涉及到生物学细节。我们先简单假定Wuhan-HU1/2019就是最早期版
: 本。其他细节等建树以后我们再fine tune。目前中国和GISAID的都是建好树了,但是
: 缺少fine tune,我现在的工作就是手工fine tune树的细节

lsunspot


【 在 keyrock (不高兴) 的大作中提到: 】
: 你的题目也写的不对
: 而且不需要码公,只要有逻辑思维能力
: 病毒复制出错就是变异,出错点是随机的,出错就是独特序列,有这个独特序列的是同源
: 如果一个病毒有多个独特序列,每个都被其他一群病毒共有,这个就是祖宗

不错,这个可操作
xiaxianyue

你显然不是码工,毫无码工的逻辑特点。正经码工写码逻辑很严密的,每一步具体怎么做,输入什么输出什么用什么算法计算很清晰。你就说说怎么定义这个“独特序列吧”。
其他更细节问题我暂不讨论。
【 在 keyrock (不高兴) 的大作中提到: 】
: 你的题目也写的不对
: 而且不需要码公,只要有逻辑思维能力
: 病毒复制出错就是变异,出错点是随机的,出错就是独特序列,有这个独特序列的是同源
: 如果一个病毒有多个独特序列,每个都被其他一群病毒共有,这个就是祖宗

xiaxianyue

laf 你要train的话100多数据数据量肯定不够,跑偏几率很高
【 在 lsunspot (小手) 的大作中提到: 】
: 按手抄本来看的话,应该迭代越多偏离越大,以前叔会考虑定义偏离算法,现在就考虑
: train个model,让model自己发现

xiaxianyue

先说说算法吧。这个是phylogenetic analysis的人做的事
【 在 lsunspot (小手) 的大作中提到: 】
: 按手抄本来看的话,应该迭代越多偏离越大,以前叔会考虑定义偏离算法,现在就考虑
: train个model,让model自己发现

keyrock

尼玛,这是论坛,谁乐意写长篇大论

我不是码公,但是逻辑严密

独特序列,顾名思义,就是你有别人没有的序列

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 你显然不是码工,毫无码工的逻辑特点。正经码工写码逻辑很严密的,每一步具体怎么
: 做,输入什么输出什么用什么算法计算很清晰。你就说说怎么定义这个“独特序列吧”。
: 其他更细节问题我暂不讨论。
: 同源

xiaxianyue

本质上phylogeny就是这个概念啊
【 在 keyrock (不高兴) 的大作中提到: 】
: 这就是一棵树,每个分支就是变异的独特序列,树根有多个分支交汇

xiaxianyue

擦,你现在是要告诉机器,什么叫独特序列,如何从100多个样品里发现独特序列。
【 在 keyrock (不高兴) 的大作中提到: 】
: 尼玛,这是论坛,谁乐意写长篇大论
: 我不是码公,但是逻辑严密
: 独特序列,顾名思义,就是你有别人没有的序列
: ”。

Spica

听起来可以写成trie,copy不一样的地方分叉,就是不知道是否效率
xiaxianyue

这东西我觉得码工搞出来真可以发篇文章。
keyrock

不用机器,手工就能干,你现在样本又没几个

100个样本,只有10个有的序列就是独特序列,如果大部分都有,就不是独特序列

超过一个样本拥有的独特序列是一个树杈,如果只有一个样本才有的序列,没有意义

树杈多的,就是祖先之一,如果树杈都能交汇到一个样本,这个是祖宗

我对生物如果追踪病毒祖先一无所知,不过我猜是这样的,不可能是其他办法

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 擦,你现在是要告诉机器,什么叫独特序列,如何从100多个样品里发现独特序列。

s
shuiya

如果假设突变最少
两两之间算word distance 然后做最小生成树
结果看看是不是make sense
gut feel 很可能不make sense

lsunspot


【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 擦,你现在是要告诉机器,什么叫独特序列,如何从100多个样品里发现独特序列。

开不同尺度的滑动窗口一小块一小块的比
p
printed

对两两节点(文件)求edit distance作为两节点间的edge weight,从而构成一张无向完全图G
然后对G求minimal spanning tree

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 你有100多份文件(并且将来还会不断有新文件传给你)。每份文件的内容大概在
29903
: 字母(目前的最大文件)到29840字母之间。每个字节只可能是A,T,C,G四个字母之
: 一,比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本,有
: 各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被发
: 掘出来后被copy成了电子版,现在要你分析哪个版本是原版。甚至有可能,有两三个原
: 版。现在把信息量最大(29903字母)发掘时间比较靠前的文件(文件名Wuhan-HU1/
: 2019)作为原始版作为root of the tree。要求你设计一个算法,把其他文件根据相似
: 度做一个树。
: 先看多少人有思路吧,之后我在细化加大难度。

xiaxianyue

这个还行。目前我的发现就是,算法处理1090来个数据,跟手工比对结果差别很大。说明算法在相似度比较近的序列比对上有严重问题。但是数据量越来越大,你不能一直靠手工比对呀
【 在 keyrock (不高兴) 的大作中提到: 】
: 不用机器,手工就能干,你现在样本又没几个
: 100个样本,只有10个有的序列就是独特序列,如果大部分都有,就不是独特序列
: 超过一个样本拥有的独特序列是一个树杈,如果只有一个样本才有的序列,没有意义: 树杈多的,就是祖先之一,如果树杈都能交汇到一个样本,这个是祖宗
: 我对生物如果追踪病毒祖先一无所知,不过我猜是这样的,不可能是其他办法

xiaxianyue

然后呢?你预想一下输出是什么
【 在 lsunspot (小手) 的大作中提到: 】
: 开不同尺度的滑动窗口一小块一小块的比

xiaxianyue

树杈多的不一定是祖先。拿measles的数据举个例子吧,你能说树梢那一长串橙点的父
节点是祖先?
【 在 keyrock (不高兴) 的大作中提到: 】
: 不用机器,手工就能干,你现在样本又没几个
: 100个样本,只有10个有的序列就是独特序列,如果大部分都有,就不是独特序列
: 超过一个样本拥有的独特序列是一个树杈,如果只有一个样本才有的序列,没有意义: 树杈多的,就是祖先之一,如果树杈都能交汇到一个样本,这个是祖宗
: 我对生物如果追踪病毒祖先一无所知,不过我猜是这样的,不可能是其他办法

keyrock

你找码公写个程序,把独特序列画成树杈,画出一张图,就容易直观看到谁是最可疑的祖先

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 这个还行。目前我的发现就是,算法处理1090来个数据,跟手工比对结果差别很大。说
: 明算法在相似度比较近的序列比对上有严重问题。但是数据量越来越大,你不能一直靠
: 手工比对呀

swjtuer

online testing,要在你痛恨的美国找工吗
keyrock

你说的对,树杈多表明分支后代多

要看是那种类型的树杈,一种是大分支树杈,下面还有好多小分支

祖先拥有更多数量大分支树杈

所以画个树图更容易看

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 树杈多的不一定是祖先。拿measles的数据举个例子吧,你能说树梢那一长串橙点的父
: 节点是祖先?

l
localdisk

这就是标准的Phylogenetic tree algorithm. 研究得太多了。首先你要定义distance.这个要根据突变的概率来算。单这个算法就是一大堆。这个也不是简单的数多少个不同就可以的。不同的距离定义会造出完全不一样的树。然后还有对树的假数,有根还是无根,结果也会大不相同。UPGMA和NJ等等还对树有不同的假设。
xiaxianyue

对,我真正想说的是,目前这些algorithms的定义和假设有问题,所以建出来的树在某些细节上跟手工比对差很多。真正的题目应该是如何在现有算法上优化树。算法都有现成的,augur/tree module
【 在 localdisk (与世无争) 的大作中提到: 】
: 这就是标准的Phylogenetic tree algorithm. 研究得太多了。首先你要定义
distance.
: 这个要根据突变的概率来算。单这个算法就是一大堆。这个也不是简单的数多少个不同
: 就可以的。不同的距离定义会造出完全不一样的树。然后还有对树的假数,有根还是无
: 根,结果也会大不相同。UPGMA和NJ等等还对树有不同的假设。

xiaxianyue

其实在blast算法的基础上修改建树效果可能更好
【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 对,我真正想说的是,目前这些algorithms的定义和假设有问题,所以建出来的树在某
: 些细节上跟手工比对差很多。真正的题目应该是如何在现有算法上优化树。算法都有现
: 成的,augur/tree module
: distance.

fishbelly

这个应该足够了

【 在 keyrock (不高兴) 的大作中提到: 】
: 你的题目也写的不对
: 而且不需要码公,只要有逻辑思维能力
: 病毒复制出错就是变异,出错点是随机的,出错就是独特序列,有这个独特序列的是同源
: 如果一个病毒有多个独特序列,每个都被其他一群病毒共有,这个就是祖宗

xiaxianyue

再借你的话评两句。外行觉得这个算法简单,那是因为他们的逻辑还流于表层,根本没开始考虑具体如何定义、输入、计算、输出这些操作。phylogenetic tree算法本身就
是一大领域,能这么轻易被几个外行解决了?
【 在 localdisk (与世无争) 的大作中提到: 】
: 这就是标准的Phylogenetic tree algorithm. 研究得太多了。首先你要定义
distance.
: 这个要根据突变的概率来算。单这个算法就是一大堆。这个也不是简单的数多少个不同
: 就可以的。不同的距离定义会造出完全不一样的树。然后还有对树的假数,有根还是无
: 根,结果也会大不相同。UPGMA和NJ等等还对树有不同的假设。

happens

这是一个数学问题

【在 xiaxianyue(下弦月)的大作中提到:】
:你有100多份文件(并且将来还会不断有新文件传给你)。每份文件的内容大概在
29903字母(目前的最大文件)到29840字母之间。每个字节只可能是A,T,C,G四个字母之
:一,比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本,有各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被发掘出来后被copy成了电子版,现在要你分析哪个版本是原版。甚至有可能,有两三个原版。现在把信息量最大(29903字母)发掘时间比较靠前的文件(文件名Wuhan-HU1/

flanker711

比较应该就是普通文本比较里用的longest Common subsequence算法吧。树里每个节点就是和母节点最小的样本。

calcityloan

看来弦月不转码工屈才了。有能力这么描述这个问题,应该可以转码。
StMicheal

这就是经典文本批判问题(textual criticism).

一个例子就是圣经文本批判,通过各种抄本的区别,判断谁先谁后承继问题。

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 你有100多份文件(并且将来还会不断有新文件传给你)。每份文件的内容大概在
29903
: 字母(目前的最大文件)到29840字母之间。每个字节只可能是A,T,C,G四个字母之
: 一,比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本,有
: 各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被发
: 掘出来后被copy成了电子版,现在要你分析哪个版本是原版。甚至有可能,有两三个原
: 版。现在把信息量最大(29903字母)发掘时间比较靠前的文件(文件名Wuhan-HU1/
: 2019)作为原始版作为root of the tree。要求你设计一个算法,把其他文件根据相似
: 度做一个树。
: 先看多少人有思路吧,之后我在细化加大难度。

l
localdisk

生物信息的情况要复杂得多。很多情况下突变几率是不相同的,比如a变成g的几率大于变成u或者c.因为RNA只有四种nucleotide,还经常会发生变过去又变回来的情况。
【 在 StMicheal (archangel) 的大作中提到: 】
: 这就是经典文本批判问题(textual criticism).
: 一个例子就是圣经文本批判,通过各种抄本的区别,判断谁先谁后承继问题。
: 29903

StMicheal

就是简化一下让lay people明白在讨论什么性质的问题。

【 在 localdisk (与世无争) 的大作中提到: 】
: 生物信息的情况要复杂得多。很多情况下突变几率是不相同的,比如a变成g的几率大于
: 变成u或者c.因为RNA只有四种nucleotide,还经常会发生变过去又变回来的情况。

xiaxianyue

其实我已经有一个大概思路了,这个树不需要用很复杂的算法,python实现应该最快。直接用find做序列比对,先整体,比对不上再break up。我python操作还是不够熟悉也没时间,要谁熟悉python愿意跟我一起试试我的算法私信我吧
【 在 calcityloan (没有昵称) 的大作中提到: 】
: 看来弦月不转码工屈才了。有能力这么描述这个问题,应该可以转码。

xiaxianyue

我仔细想了一下滑窗是很经典的序列比对方式。但用在这个数据库里效率太低。这个数据库有>99%的相似度,不应该从局部开始比对
【 在 lsunspot (小手) 的大作中提到: 】
: 开不同尺度的滑动窗口一小块一小块的比

l
localdisk

没那么简单。如果仅仅是置换当然简单,但难点在有insertion/deletion。如果多了/
少了一两个,你就要猜了。
【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 其实我已经有一个大概思路了,这个树不需要用很复杂的算法,python实现应该最快。
: 直接用find做序列比对,先整体,比对不上再break up。我python操作还是不够熟悉也
: 没时间,要谁熟悉python愿意跟我一起试试我的算法私信我吧

xiaxianyue

对,门外汉想凑热闹只能这么跟他们说。实际上更复杂,得手把手有思路了后再慢慢加大难度和细节。
【 在 StMicheal (archangel) 的大作中提到: 】
: 就是简化一下让lay people明白在讨论什么性质的问题。

xiaxianyue

目前就你跟得上思路。所以我的算法第二步就是根据query跟subject(wuhan-hu1/2019)的比对结果,输出几个数据到两个dictionary里。一个是insertion/deletoon
dictionary,一个是mutation dictionary。建树是根据两个dictionary来建。再复杂
一点可以自己定义class。
【 在 localdisk (与世无争) 的大作中提到: 】
: 没那么简单。如果仅仅是置换当然简单,但难点在有insertion/deletion。如果多了/
: 少了一两个,你就要猜了。

CatchGodLine

这个要用hash字典记录所有的独特序列点,位置和发生在那个样本上,一定同时用
resize sliding Windows在所有样本同时比,最后hash表里独特序列最少的就是母本。不敢说完全正确。

kingcw


Printed的方法就可以了,用dynamic programming算pair文件间的minimum edit
distance,然后拿minimum spanning tree
TheMatrix

有道理。

【 在 CatchGodLine (捆仙绳) 的大作中提到: 】
: 这个要用hash字典记录所有的独特序列点,位置和发生在那个样本上,一定同时用
: resize sliding Windows在所有样本同时比,最后hash表里独特序列最少的就是母本。
: 不敢说完全正确。

kingcw


原版的定义你没有,如果minimum weight树杈最多的不一定是原版,可能是变异的话,你怎么定义原版?
niuheliang

你这个很简单,也不需要假定哪一个版本是最初版。1990年代初的时候我就写过,用来自动分析故意被感染计算机病毒的EXE/COM文件。字节长度也大得多。

我给你的建议是不要再跟这个问题。有能力做这种自动分析的没有几十万也有几万人。早就应该有人分析出来了只不过不吭声。这不是什么技术问题,而是政治问题。这也是后来我的教授们给我的建议。

不要做有用的人。别人聪明得很,你装糊涂,日子会过得comfortable。不然即使是蓝
皮,也难保有人往你怀里塞本红皮让你去中国自首。

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 这个确实很关键,也涉及到生物学细节。我们先简单假定Wuhan-HU1/2019就是最早期版
: 本。其他细节等建树以后我们再fine tune。目前中国和GISAID的都是建好树了,但是
: 缺少fine tune,我现在的工作就是手工fine tune树的细节

CatchGodLine

想了一下最小距离 恐怕不合适

因为数据连续 没有固定的DNA词汇表

没有原本

所以和经典圣经问题不全一样

xiaxianyue

hash只是生成方式。实际上这个字典entries应该包括突变位点对应subject的index,
该index突变成对应值需要多少entropy(“抄错”的难度),该index突变成对应值的
event数(几个手抄本出现这个错误),该突变是否造成了错义突变(抄错是否改变读者
对内容的理解)。最后是根据突变的频率,难度,和错误严重程度来建树。
【 在 CatchGodLine (捆仙绳) 的大作中提到: 】
: 这个要用hash字典记录所有的独特序列点,位置和发生在那个样本上,一定同时用
: resize sliding Windows在所有样本同时比,最后hash表里独特序列最少的就是母本。
: 不敢说完全正确。

xiaxianyue

你就当这题是个brain teaser吧
【 在 niuheliang (别问我是谁) 的大作中提到: 】
: 你这个很简单,也不需要假定哪一个版本是最初版。1990年代初的时候我就写过,用来
: 自动分析故意被感染计算机病毒的EXE/COM文件。字节长度也大得多。
: 我给你的建议是不要再跟这个问题。有能力做这种自动分析的没有几十万也有几万人。
: 早就应该有人分析出来了只不过不吭声。这不是什么技术问题,而是政治问题。这也是
: 后来我的教授们给我的建议。
: 不要做有用的人。别人聪明得很,你装糊涂,日子会过得comfortable。不然即使是蓝
: 皮,也难保有人往你怀里塞本红皮让你去中国自首。

CatchGodLine


听起来你的问题已经解决了

不错

【 在 xiaxianyue(下弦月) 的大作中提到: 】

: hash只是生成方式。实际上这个字典entries应该包括突变位点对应subject的
index,

: 该index突变成对应值需要多少entropy(“抄错”的难度),该index突变成对
应值的

: event数(几个手抄本出现这个错误),该突变是否造成了错义突变(抄错是否改
变读者

: 对内容的理解)。最后是根据突变的频率,难度,和错误严重程度来建树。

keyrock

灌装病毒问题写程序是舍近求远

灌装病毒总共出来不到半年,变异也没多少,手画都能看出来

没事就想写程序,也不动动脑子需要吗
TheMatrix

假设100个总样品,所有样本头和尾都可以对齐,假设其中98个样品在x位置处有A,另
外两个在该处为G。怎么确认A是突变的还是G是突变的?

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: hash只是生成方式。实际上这个字典entries应该包括突变位点对应subject的index,
: 该index突变成对应值需要多少entropy(“抄错”的难度),该index突变成对应值的
: event数(几个手抄本出现这个错误),该突变是否造成了错义突变(抄错是否改变读者
: 对内容的理解)。最后是根据突变的频率,难度,和错误严重程度来建树。

Cadillaclee

洗脚姐,看来真是伪码工,什么干货也没给,你是怎么进的google

【 在 swjtuer (码农的小船说翻就翻) 的大作中提到: 】
: online testing,要在你痛恨的美国找工吗

TheMatrix

算是能算出来,但是结果的物理意义不清楚啊。

【 在 kingcw (无语了) 的大作中提到: 】
: Printed的方法就可以了,用dynamic programming算pair文件间的minimum edit
: distance,然后拿minimum spanning tree

xiaxianyue

你的假设就错了。为啥头尾就一定能对齐?我出题的时候都告诉你文件大小在一个范围之内。读题不仔细,扣分
【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 假设100个总样品,所有样本头和尾都可以对齐,假设其中98个样品在x位置处有A,另
: 外两个在该处为G。怎么确认A是突变的还是G是突变的?

xiaxianyue

但是我python实际操作不行,要找个熟练公写代码跑一下,把树建出来再验证。
【 在 CatchGodLine (捆仙绳) 的大作中提到: 】
: 听起来你的问题已经解决了
: 不错
:
: hash只是生成方式。实际上这个字典entries应该包括突变位点对应subject的: index,
:
: 该index突变成对应值需要多少entropy(“抄错”的难度),该index突变成对
: 应值的
:
: event数(几个手抄本出现这个错误),该突变是否造成了错义突变(抄错是否改
: 变读者
:
: 对内容的理解)。最后是根据突变的频率,难度,和错误严重程度来建树。
:

StMicheal

再提供一个考虑,可以减少点复杂性。好比同一个弹坑两次着弹的几率可以忽略不记。同一个碱基多次变异的几率也可以不用考虑。
kingcw

他的问题是按照相似度建树啊,minimum edit distance就是相似度最近的,minimum
weight树杈最多的就是原版

除非他重新定义相似度,give data meaning,不然string comparison不就是这个

[在 TheMatrix (TheMatrix) 的大作中提到:]
:算是能算出来,但是结果的物理意义不清楚啊。
:☆ 发自 iPhone 买买提 1.24.11
DAYAFTERTMR

这个问题能回答你的最优群体不是码工,码工学的是比较成熟且基本的算法,在你给出的限制条件下,运行结果很可能差强人意。女神加油。

xiaxianyue

因为码工本身不理解相似的生物学含义。他们算出来相似,但解释不了是什么相似。
【 在 DAYAFTERTMR (明天过后) 的大作中提到: 】
: 这个问题能回答你的最优群体不是码工,玛工学的是比较成熟且基本的算法,在你给出
: 的限制条件下,运行结果很可能差强人意。女神加油。

TheMatrix

是个数学问题,但是个open ended数学问题。

假设所有样本都可以对齐,给个坐标从1到30000。然后所有位置上多于一个变化的坐标列出来,记为集合X,并记录其对应的变化的集合M_x,每一个x有一个集合。

函数空间,X到M,每一个x要映射到对应的M_x。每一个函数都可以作为祖先给出一个合理发展树。然后标记每个发展树的概率...

【 在 happens (happens) 的大作中提到: 】
: 这是一个数学问题
: :你有100多份文件(并且将来还会不断有新文件传给你)。每份文件的内容大概在
: 29903字母(目前的最大文件)到29840字母之间。每个字节只可能是A,T,C,G四个字
: 母之
: :一,比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本,
: 有各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被
: 发掘出来后被copy成了电子版,现在要你分析哪个版本是原版。甚至有可能,有两三个
: 原版。现在把信息量最大(29903字母)发掘时间比较靠前的文件(文件名Wuhan-HU1/

xiaxianyue

不属实。突变有热点区。或者说,可能很多份手抄本都是由同一份父本来的,比如老师布置作业让一堆学生都抄一份。目前统计最多的点突变有3份样品符合。这是建子树的
基础,很重要。
【 在 StMicheal (archangel) 的大作中提到: 】
: 再提供一个考虑,可以减少点复杂性。好比同一个弹坑两次着弹的几率可以忽略不记。
: 同一个碱基多次变异的几率也可以不用考虑。

TheMatrix

我知道,文件大小是在一个范围内,但是还是有头有尾啊。而且还能找到大量互相
match的片段作为对准依据。我假设头尾能对齐,不仅头尾能对齐,中间也有大量能对
齐。还得给出统一的坐标。这步算“预处理”。:)

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 你的假设就错了。为啥头尾就一定能对齐?我出题的时候都告诉你文件大小在一个范围
: 之内。读题不仔细,扣分

TheMatrix

对,这个表达为在祖先path上不能在一个点上多次变异。

【 在 StMicheal (archangel) 的大作中提到: 】
: 再提供一个考虑,可以减少点复杂性。好比同一个弹坑两次着弹的几率可以忽略不记。
: 同一个碱基多次变异的几率也可以不用考虑。

s
swanswan

帮你写代码有啥好处?马工都精着呢。

FrancisNg

神马屄题?
日后再解!

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 你有100多份文件(并且将来还会不断有新文件传给你)。每份文件的内容大概在
29903
: 字母(目前的最大文件)到29840字母之间。每个字节只可能是A,T,C,G四个字母之
: 一,比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本,有
: 各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被发
: 掘出来后被copy成了电子版,现在要你分析哪个版本是原版。甚至有可能,有两三个原
: 版。现在把信息量最大(29903字母)发掘时间比较靠前的文件(文件名Wuhan-HU1/
: 2019)作为原始版作为root of the tree。要求你设计一个算法,把其他文件根据相似
: 度做一个树。
: 先看多少人有思路吧,之后我在细化加大难度。

kingcw


一天能写完吗?我倒是在做跟covid-19有关的事,所以感兴趣
CatchGodLine


写这代码大概要一个小时呢

用hash的目的是保证独特序列统计在不同样本中出现次数和位置

前提条件是后代样本的某些独特序列不会突变回去母本 生物上有这个可能性吗?

如果生物有这个可能性 那么在数学上就不可能找到母本了

另外因为不知道特征序列到底有多长 所以使用可变滑动窗口可以提高效率

这些样本的数据量很小 所以不用考虑O(lgN)问题 O(N)就可以

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 但是我python实际操作不行,要找个熟练公写代码跑一下,把树建出来再验证。

TheMatrix

一个小时能写完?

【 在 CatchGodLine (捆仙绳) 的大作中提到: 】
: 写这代码大概要一个小时呢
: 用hash的目的是保证独特序列统计在不同样本中出现次数和位置
: 前提条件是后代样本的某些独特序列不会突变回去母本 生物上有这个可能性吗?
: 如果生物有这个可能性 那么在数学上就不可能找到母本了
: 另外因为不知道特征序列到底有多长 所以使用可变滑动窗口可以提高效率
: 这些样本的数据量很小 所以不用考虑O(lgN)问题 O(N)就可以

xiaxianyue

这东西写出来以后会非常有用。特别是突发性流行病大数据研究方面,绝对牛逼。事实上phylogenetic tree怎么算,要先考虑整个数据库的整体相似性。这个用目前的算法
可以给个百分比。如果相似度及其高(90%以上,且基因组小)用我的算法准确率远远
大于传统算法。传统算法是为差异度大的数据库设计的。
【 在 CatchGodLine (捆仙绳) 的大作中提到: 】
: 写这代码大概要一个小时呢
: 用hash的目的是保证独特序列统计在不同样本中出现次数和位置
: 前提条件是后代样本的某些独特序列不会突变回去母本 生物上有这个可能性吗?
: 如果生物有这个可能性 那么在数学上就不可能找到母本了
: 另外因为不知道特征序列到底有多长 所以使用可变滑动窗口可以提高效率
: 这些样本的数据量很小 所以不用考虑O(lgN)问题 O(N)就可以

IGvsNaVi

感觉是个 unsupervised learning 问题,需要定义一下不同序列的距离(这个估计有
现成的算法),有了距离以后就可以调包了,Python有很多unsupervided learning包
,别的语言也有。比如 Hierarchical_clustering https://en.m.wikipedia.org/wiki/Hierarchical_clustering,再比如k_means,em。。。等算法

看看如何根据距离把它们clustering。
这种方法不需要根序列,只需要所有的序列以及如何计算各个序列之间的差异大小(距离,或者什么别的score)

CatchGodLine


不能用 unsupervised learning

无法采用类W2W距离算法

【 在 IGvsNaVi (IGforever) 的大作中提到: 】
: 感觉是个 unsupervised learning 问题,需要定义一下不同序列的距离(这个估计有
: 现成的算法),有了距离以后就可以调包了,Python有很多unsupervided learning包
: ,别的语言也有。比如 Hierarchical_clustering
: https://en.m.wikipedia.org/wiki/Hierarchical_clustering,再比如k_means,em。
: 。。等算法
: 看看如何根据距离把它们clustering。
: 这种方法不需要根序列,只需要所有的序列以及如何计算各个序列之间的差异大小(距
: 离,或者什么别的score)

r
rpman

有similarity matrix后就是个找minimum cost spanning tree
similarity matrix怎么定义就需要生物学知识了。。举个例子,可以基于Levenshtein上加点heuristics
DAYAFTERTMR


找一个自己学校计算机系的感兴趣的助理教授合作好一些,自己只要是一作加通讯就好了。

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 因为码工本身不理解相似的生物学含义。他们算出来相似,但解释不了是什么相似。

r
rpman

formalize一点的话实际上应该有一个算突变概率的函数P, 进化路径是一条马尔科夫链
xiaxianyue

你会python的话用class定义更方便。hashtable用来做基因组突变难度的reference
【 在 CatchGodLine (捆仙绳) 的大作中提到: 】
: 写这代码大概要一个小时呢
: 用hash的目的是保证独特序列统计在不同样本中出现次数和位置
: 前提条件是后代样本的某些独特序列不会突变回去母本 生物上有这个可能性吗?
: 如果生物有这个可能性 那么在数学上就不可能找到母本了
: 另外因为不知道特征序列到底有多长 所以使用可变滑动窗口可以提高效率
: 这些样本的数据量很小 所以不用考虑O(lgN)问题 O(N)就可以

xiaxianyue

我手动算了一下,实际情况更加复杂,这个算法还要优化。如果是头上缺失或者中部的插入/缺失,要用扣分方式排序加建子分支。另外,在发现gap(包括头部缺失),要在其他文件里搜索该“特征”,做cluster。mismatch一般在0-6个之间,很难用来判断父子关系,我大概会以减分的方式排序吧。
尾部的缺失要用加分的方式排序,权重要放得小一点。
【 在 CatchGodLine (捆仙绳) 的大作中提到: 】
: 写这代码大概要一个小时呢
: 用hash的目的是保证独特序列统计在不同样本中出现次数和位置
: 前提条件是后代样本的某些独特序列不会突变回去母本 生物上有这个可能性吗?
: 如果生物有这个可能性 那么在数学上就不可能找到母本了
: 另外因为不知道特征序列到底有多长 所以使用可变滑动窗口可以提高效率
: 这些样本的数据量很小 所以不用考虑O(lgN)问题 O(N)就可以

hsh

这是字符串比较的问题,和发现文档的不同版本有哪些改变基本是一样的问题,具体算法嘛,我不会,但是现在已经有现成的解决方案了。需要假设一个根,Wuhan-01比较合理。

圣经手抄本更复杂一些,因为不能假设根,而是要找到根。

每个变化怎样数字化表达需要生物学知识。

怎样算是同一个树枝,也需要生物学知识。

这个问题还是很有价值的

newIdRobot

有真实数据么? 可以跑出来看看结果

【在 xiaxianyue(下弦月)的大作中提到:】
:你有100多份文件(并且将来还会不断有新文件传给你)。每份文件的内容大概在
29903字母(目前的最大文件)到29840字母之间。每个字节只可能是A,T,C,G四个字母之
:一,比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本,有各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被发掘出来后被copy成了电子版,现在要你分析哪个版本是原版。甚至有可能,有两三个原版。现在把信息量最大(29903字母)发掘时间比较靠前的文件(文件名Wuhan-HU1/

newIdRobot

她学术水平搭不上cs ap 吧。要“牺牲”很大,人家才能帮她。

【在 DAYAFTERTMR(明天过后)的大作中提到:】

:找一个自己学校计算机系的感兴趣的助理教授合作好一些,自己只要是一作加通讯就好了。

n
nova999

听说过哈夫曼编码吗?
可以先搜索最长相似字段建字典库。然后用哈夫曼编码比较。

:)

SiegeCat

第一页已经给出标准的正确答案了,其他人都在胡说八道

稍微解释一下 100 c 2 大概是5000个边。

整个图每一个顶点就是一个基因编码文件,每个边将两个文件相连。

通过某种模型判断出两个文件距离是多少,记录在这个边上,比方说简单的模型可以是最小编辑距离(即一个文件变成另一个文件最小改变数)。

接着只要求出整个图的最小生成树即可,complexity是 O(E*N^2) + O(ELogV)
E是文件对儿,也就是5000左右
N是每个文件大小
V是文件数量

【 在 printed () 的大作中提到: 】
: 对两两节点(文件)求edit distance作为两节点间的edge weight,从而构成一张无向
: 完全图G
: 然后对G求minimal spanning tree
: 29903

P
Peppy

看了一遍回复,差点把我这个53的给笑昏过去了。就100多个样本还要写程序,手动比
较两个小时肯定出结果了。

当然需要必要的工具。非马公的不太可能知道这些专业工具。

H
HarryAwesome

应该是AUCG
l
localdisk

你牛!每个序列3万个字母,你一个一个去比。

看完回复我充分理解了眼高手低这个词。
【 在 Peppy (又是一个良民) 的大作中提到: 】
: 看了一遍回复,差点把我这个53的给笑昏过去了。就100多个样本还要写程序,手动比
: 较两个小时肯定出结果了。
: 当然需要必要的工具。非马公的不太可能知道这些专业工具。

xiaxianyue

所以我都懒得跟一些人争
【 在 localdisk (与世无争) 的大作中提到: 】
: 你牛!每个序列3万个字母,你一个一个去比。
: 看完回复我充分理解了眼高手低这个词。

P
Peppy

无知者无畏,什么都敢说
[在 localdisk (与世无争) 的大作中提到:]
:你牛!每个序列3万个字母,你一个一个去比。
:看完回复我充分理解了眼高手低这个词。
k
kendallmit

这些全世界各地上传的测序数据,都有不可避免的sequencing error,也是各种noise
,不能都认定为突变,除非特定突变在多个测序数据里稳定出现了。

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 这个确实很关键,也涉及到生物学细节。我们先简单假定Wuhan-HU1/2019就是最早期版
: 本。其他细节等建树以后我们再fine tune。目前中国和GISAID的都是建好树了,但是
: 缺少fine tune,我现在的工作就是手工fine tune树的细节

Y
YXLM

  无责任瞎给一个简便算法。

  先假定长度一样,内部没有整段的错位,只有个别不同。
  这个好算吧?
  只要规定分数即可。如果有100份,在某一位置上,如果100都相同,就都得100分
(或都不得分)。如果99份相同,这99份都得99分,剩下1份得1分(等于扣了98分)。  这样算下来,分数最高的就是原件。
  当然,也可以改变权重,例如,连错3个按错2个半扣分,等等。

  对于错位、短缺或冗余,经过处理后,也可以使用上述原则。当然,最麻烦的就是错位。只有出现在两端的,才单纯是短缺和冗余,短缺和冗余是错位的特例。
  错位怎么处理?
  就是识别片段。即哪些部分是长度不变的。可以规定一个分数范围,只要长度不变,内容差不多的,都可以识别为片段。片段内部的差异可以直接算分。

  注意:对于有些体系,识别片段必须预估错位程度。你不能把某一份的开头片段,识别为和另一份的中间片段是一段,那就麻烦了,没法比较了(我的意思是说,我不打算想算法了)。
  我们必须假设,错位是有限度的,只比较接近位置以识别片段。

  识别完片段。对于片段的短缺,和片段间的冗余,都可以分别算分。注意这个地方,可能更需要改变权重,例如,增加三个,按错1个半扣分,之类。
TheMatrix

看第一段算法大意,有一定合理性。

【 在 YXLM (非要昵称不可吗) 的大作中提到: 】
:   无责任瞎给一个简便算法。
:   先假定长度一样,内部没有整段的错位,只有个别不同。
:   这个好算吧?
:   只要规定分数即可。如果有100份,在某一位置上,如果100都相同,就都得100分
: (或都不得分)。如果99份相同,这99份都得99分,剩下1份得1分(等于扣了98分)。
:   这样算下来,分数最高的就是原件。
:   当然,也可以改变权重,例如,连错3个按错2个半扣分,等等。
:   对于错位、短缺或冗余,经过处理后,也可以使用上述原则。当然,最麻烦的就是
: 错位。只有出现在两端的,才单纯是短缺和冗余,短缺和冗余是错位的特例。
:   错位怎么处理?
: ...................

TheMatrix

我不是抬杠,minimum weight spanning tree,这个得到了。树杈多的是原版,这句话能这么说吗?还是这是定论?

【 在 kingcw (无语了) 的大作中提到: 】
: 他的问题是按照相似度建树啊,minimum edit distance就是相似度最近的,minimum
: weight树杈最多的就是原版
: 除非他重新定义相似度,give data meaning,不然string comparison不就是这个
: [在 TheMatrix (TheMatrix) 的大作中提到:]
: :算是能算出来,但是结果的物理意义不清楚啊。
: :☆ 发自 iPhone 买买提 1.24.11

TheMatrix

标准正确答案?什么问题的标准正确答案啊?

【 在 SiegeCat () 的大作中提到: 】
: 第一页已经给出标准的正确答案了,其他人都在胡说八道
: 稍微解释一下 100 c 2 大概是5000个边。
: 整个图每一个顶点就是一个基因编码文件,每个边将两个文件相连。
: 通过某种模型判断出两个文件距离是多少,记录在这个边上,比方说简单的模型可以是
: 最小编辑距离(即一个文件变成另一个文件最小改变数)。
: 接着只要求出整个图的最小生成树即可,complexity是 O(E*N^2) + O(ELogV)
: E是文件对儿,也就是5000左右
: N是每个文件大小
: V是文件数量

S
SLE

计算每两个文件的距离,定义为从一个文件变成另一个文件需要的最少错误数。
然后找到这个图里的最小树。
再然后,如果你知道哪一个文件是原始文件,就可以得到所有文件的传承顺序。

【 在 xiaxianyue (下弦月) 的大作中提到: 】
: 你有100多份文件(并且将来还会不断有新文件传给你)。每份文件的内容大概在
29903
: 字母(目前的最大文件)到29840字母之间。每个字节只可能是A,T,C,G四个字母之
: 一,比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本,有
: 各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被发
: 掘出来后被copy成了电子版,现在要你分析哪个版本是原版。甚至有可能,有两三个原
: 版。现在把信息量最大(29903字母)发掘时间比较靠前的文件(文件名Wuhan-HU1/
: 2019)作为原始版作为root of the tree。要求你设计一个算法,把其他文件根据相似
: 度做一个树。
: 先看多少人有思路吧,之后我在细化加大难度。

TheMatrix

哦,树根定在已知的原始文件上,纲举目张,有道理。那如果不知道原始文件而要找原始文件,那就不行了,对吧?

【 在 SLE (嗯,就这样定了。) 的大作中提到: 】
: 计算每两个文件的距离,定义为从一个文件变成另一个文件需要的最少错误数。
: 然后找到这个图里的最小树。
: 再然后,如果你知道哪一个文件是原始文件,就可以得到所有文件的传承顺序。
: 29903

S
SLE

可以寻找使得树的深度最小的根。
【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 哦,树根定在已知的原始文件上,纲举目张,有道理。那如果不知道原始文件而要找原
: 始文件,那就不行了,对吧?

kingcw

找root node可以用leader election,这个算法自己定义

譬如选择weight为0的几个文件,也就是相同的文件最多的当leader,etc

这个问题没有讨论下去的必要了,浪费时间,楼主显然把这个版当成生物版了

[在 TheMatrix (TheMatrix) 的大作中提到:]
:我不是抬杠,minimum weight spanning tree,这个得到了。树杈多的是原版,这句
话能这么说吗?还是这是定论?
:☆ 发自 iPhone 买买提 1.24.11