x********e
发帖数: 35261 | 1 你有100多份文件（并且将来还会不断有新文件传给你）。每份文件的内容大概在29903
字母（目前的最大文件）到29840字母之间。每个字节只可能是A，T，C，G四个字母之
一，比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本，有
各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被发
掘出来后被copy成了电子版，现在要你分析哪个版本是原版。甚至有可能，有两三个原
版。现在把信息量最大（29903字母）发掘时间比较靠前的文件（文件名Wuhan-HU1/
2019）作为原始版作为root of the tree。要求你设计一个算法，把其他文件根据相似
度做一个树。
先看多少人有思路吧，之后我在细化加大难度。 |
l******t
发帖数: 55733 | 2 缺如何决定先后的条件吧？就是AI也得先能supervised啊 |
x********e
发帖数: 35261 | 3 这个确实很关键，也涉及到生物学细节。我们先简单假定Wuhan-HU1/2019就是最早期版
本。其他细节等建树以后我们再fine tune。目前中国和GISAID的都是建好树了，但是
缺少fine tune，我现在的工作就是手工fine tune树的细节
【在 l******t 的大作中提到】
: 缺如何决定先后的条件吧？就是AI也得先能supervised啊
|
k*****k
发帖数: 1 | 4 你的题目也写的不对
而且不需要码公，只要有逻辑思维能力
病毒复制出错就是变异，出错点是随机的，出错就是独特序列，有这个独特序列的是同源
如果一个病毒有多个独特序列，每个都被其他一群病毒共有，这个就是祖宗 |
k*****k
发帖数: 1 | 5 这就是一棵树，每个分支就是变异的独特序列，树根有多个分支交汇 |
l******t
发帖数: 55733 | 6 按手抄本来看的话，应该迭代越多偏离越大，以前叔会考虑定义偏离算法，现在就考虑
train个model，让model自己发现
【在 x********e 的大作中提到】
: 这个确实很关键，也涉及到生物学细节。我们先简单假定Wuhan-HU1/2019就是最早期版
: 本。其他细节等建树以后我们再fine tune。目前中国和GISAID的都是建好树了，但是
: 缺少fine tune，我现在的工作就是手工fine tune树的细节
|
l******t
发帖数: 55733 | 7
同源
不错，这个可操作
【在 k*****k 的大作中提到】
: 你的题目也写的不对
: 而且不需要码公，只要有逻辑思维能力
: 病毒复制出错就是变异，出错点是随机的，出错就是独特序列，有这个独特序列的是同源
: 如果一个病毒有多个独特序列，每个都被其他一群病毒共有，这个就是祖宗
|
x********e
发帖数: 35261 | 8 你显然不是码工，毫无码工的逻辑特点。正经码工写码逻辑很严密的，每一步具体怎么
做，输入什么输出什么用什么算法计算很清晰。你就说说怎么定义这个“独特序列吧”。
其他更细节问题我暂不讨论。
同源
【在 k*****k 的大作中提到】
: 你的题目也写的不对
: 而且不需要码公，只要有逻辑思维能力
: 病毒复制出错就是变异，出错点是随机的，出错就是独特序列，有这个独特序列的是同源
: 如果一个病毒有多个独特序列，每个都被其他一群病毒共有，这个就是祖宗
|
x********e
发帖数: 35261 | 9 laf 你要train的话100多数据数据量肯定不够，跑偏几率很高
【在 l******t 的大作中提到】
: 按手抄本来看的话，应该迭代越多偏离越大，以前叔会考虑定义偏离算法，现在就考虑
: train个model，让model自己发现
|
x********e
发帖数: 35261 | 10 先说说算法吧。这个是phylogenetic analysis的人做的事
【在 l******t 的大作中提到】
: 按手抄本来看的话，应该迭代越多偏离越大，以前叔会考虑定义偏离算法，现在就考虑
: train个model，让model自己发现
|
|
|
k*****k
发帖数: 1 | 11 尼玛，这是论坛，谁乐意写长篇大论
我不是码公，但是逻辑严密
独特序列，顾名思义，就是你有别人没有的序列
”。
【在 x********e 的大作中提到】
: 你显然不是码工，毫无码工的逻辑特点。正经码工写码逻辑很严密的，每一步具体怎么
: 做，输入什么输出什么用什么算法计算很清晰。你就说说怎么定义这个“独特序列吧”。
: 其他更细节问题我暂不讨论。
:
: 同源
|
x********e
发帖数: 35261 | 12 本质上phylogeny就是这个概念啊
【在 k*****k 的大作中提到】
: 这就是一棵树，每个分支就是变异的独特序列，树根有多个分支交汇
|
x********e
发帖数: 35261 | 13 擦，你现在是要告诉机器，什么叫独特序列，如何从100多个样品里发现独特序列。
【在 k*****k 的大作中提到】
: 尼玛，这是论坛，谁乐意写长篇大论
: 我不是码公，但是逻辑严密
: 独特序列，顾名思义，就是你有别人没有的序列
:
: ”。
|
S***a
发帖数: 934 | 14 听起来可以写成trie，copy不一样的地方分叉，就是不知道是否效率 |
x********e
发帖数: 35261 | |
k*****k
发帖数: 1 | 16 不用机器，手工就能干，你现在样本又没几个
100个样本，只有10个有的序列就是独特序列，如果大部分都有，就不是独特序列
超过一个样本拥有的独特序列是一个树杈，如果只有一个样本才有的序列，没有意义
树杈多的，就是祖先之一，如果树杈都能交汇到一个样本，这个是祖宗
我对生物如果追踪病毒祖先一无所知，不过我猜是这样的，不可能是其他办法
【在 x********e 的大作中提到】
: 擦，你现在是要告诉机器，什么叫独特序列，如何从100多个样品里发现独特序列。
|
s****a
发帖数: 794 | 17 如果假设突变最少
两两之间算word distance 然后做最小生成树
结果看看是不是make sense
gut feel 很可能不make sense |
l******t
发帖数: 55733 | 18
开不同尺度的滑动窗口一小块一小块的比
【在 x********e 的大作中提到】
: 擦，你现在是要告诉机器，什么叫独特序列，如何从100多个样品里发现独特序列。
|
p*****d
发帖数: 183 | 19 对两两节点（文件）求edit distance作为两节点间的edge weight，从而构成一张无向
完全图G
然后对G求minimal spanning tree
29903
【在 x********e 的大作中提到】
: 你有100多份文件（并且将来还会不断有新文件传给你）。每份文件的内容大概在29903
: 字母（目前的最大文件）到29840字母之间。每个字节只可能是A，T，C，G四个字母之
: 一，比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本，有
: 各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被发
: 掘出来后被copy成了电子版，现在要你分析哪个版本是原版。甚至有可能，有两三个原
: 版。现在把信息量最大（29903字母）发掘时间比较靠前的文件（文件名Wuhan-HU1/
: 2019）作为原始版作为root of the tree。要求你设计一个算法，把其他文件根据相似
: 度做一个树。
: 先看多少人有思路吧，之后我在细化加大难度。
|
x********e
发帖数: 35261 | 20 这个还行。目前我的发现就是，算法处理1090来个数据，跟手工比对结果差别很大。说
明算法在相似度比较近的序列比对上有严重问题。但是数据量越来越大，你不能一直靠
手工比对呀
【在 k*****k 的大作中提到】
: 不用机器，手工就能干，你现在样本又没几个
: 100个样本，只有10个有的序列就是独特序列，如果大部分都有，就不是独特序列
: 超过一个样本拥有的独特序列是一个树杈，如果只有一个样本才有的序列，没有意义
: 树杈多的，就是祖先之一，如果树杈都能交汇到一个样本，这个是祖宗
: 我对生物如果追踪病毒祖先一无所知，不过我猜是这样的，不可能是其他办法
|
|
|
x********e
发帖数: 35261 | 21 然后呢？你预想一下输出是什么
【在 l******t 的大作中提到】
:
: 开不同尺度的滑动窗口一小块一小块的比
|
x********e
发帖数: 35261 | 22 树杈多的不一定是祖先。拿measles的数据举个例子吧，你能说树梢那一长串橙点的父
节点是祖先？
【在 k*****k 的大作中提到】
: 不用机器，手工就能干，你现在样本又没几个
: 100个样本，只有10个有的序列就是独特序列，如果大部分都有，就不是独特序列
: 超过一个样本拥有的独特序列是一个树杈，如果只有一个样本才有的序列，没有意义
: 树杈多的，就是祖先之一，如果树杈都能交汇到一个样本，这个是祖宗
: 我对生物如果追踪病毒祖先一无所知，不过我猜是这样的，不可能是其他办法
|
k*****k
发帖数: 1 | 23 你找码公写个程序，把独特序列画成树杈，画出一张图，就容易直观看到谁是最可疑的
祖先
【在 x********e 的大作中提到】
: 这个还行。目前我的发现就是，算法处理1090来个数据，跟手工比对结果差别很大。说
: 明算法在相似度比较近的序列比对上有严重问题。但是数据量越来越大，你不能一直靠
: 手工比对呀
|
s*****r
发帖数: 43070 | 24 online testing，要在你痛恨的美国找工吗 |
k*****k
发帖数: 1 | 25 你说的对，树杈多表明分支后代多
要看是那种类型的树杈，一种是大分支树杈，下面还有好多小分支
祖先拥有更多数量大分支树杈
所以画个树图更容易看
【在 x********e 的大作中提到】
: 树杈多的不一定是祖先。拿measles的数据举个例子吧，你能说树梢那一长串橙点的父
: 节点是祖先？
|
l*******k
发帖数: 922 | 26 这就是标准的Phylogenetic tree algorithm. 研究得太多了。首先你要定义distance.
这个要根据突变的概率来算。单这个算法就是一大堆。这个也不是简单的数多少个不同
就可以的。不同的距离定义会造出完全不一样的树。然后还有对树的假数，有根还是无
根，结果也会大不相同。UPGMA和NJ等等还对树有不同的假设。 |
x********e
发帖数: 35261 | 27 对，我真正想说的是，目前这些algorithms的定义和假设有问题，所以建出来的树在某
些细节上跟手工比对差很多。真正的题目应该是如何在现有算法上优化树。算法都有现
成的，augur/tree module
distance.
【在 l*******k 的大作中提到】
: 这就是标准的Phylogenetic tree algorithm. 研究得太多了。首先你要定义distance.
: 这个要根据突变的概率来算。单这个算法就是一大堆。这个也不是简单的数多少个不同
: 就可以的。不同的距离定义会造出完全不一样的树。然后还有对树的假数，有根还是无
: 根，结果也会大不相同。UPGMA和NJ等等还对树有不同的假设。
|
x********e
发帖数: 35261 | 28 其实在blast算法的基础上修改建树效果可能更好
【在 x********e 的大作中提到】
: 对，我真正想说的是，目前这些algorithms的定义和假设有问题，所以建出来的树在某
: 些细节上跟手工比对差很多。真正的题目应该是如何在现有算法上优化树。算法都有现
: 成的，augur/tree module
:
: distance.
|
f*******y
发帖数: 470 | 29 这个应该足够了
同源
【在 k*****k 的大作中提到】
: 你的题目也写的不对
: 而且不需要码公，只要有逻辑思维能力
: 病毒复制出错就是变异，出错点是随机的，出错就是独特序列，有这个独特序列的是同源
: 如果一个病毒有多个独特序列，每个都被其他一群病毒共有，这个就是祖宗
|
x********e
发帖数: 35261 | 30 再借你的话评两句。外行觉得这个算法简单，那是因为他们的逻辑还流于表层，根本没
开始考虑具体如何定义、输入、计算、输出这些操作。phylogenetic tree算法本身就
是一大领域，能这么轻易被几个外行解决了？
distance.
【在 l*******k 的大作中提到】
: 这就是标准的Phylogenetic tree algorithm. 研究得太多了。首先你要定义distance.
: 这个要根据突变的概率来算。单这个算法就是一大堆。这个也不是简单的数多少个不同
: 就可以的。不同的距离定义会造出完全不一样的树。然后还有对树的假数，有根还是无
: 根，结果也会大不相同。UPGMA和NJ等等还对树有不同的假设。
|
|
|
h*****s
发帖数: 733 | 31 这是一个数学问题
：你有100多份文件（并且将来还会不断有新文件传给你）。每份文件的内容大概在
29903字母（目前的最大文件）到29840字母之间。每个字节只可能是A，T，C，G四个字
母之
：一，比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本，
有各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被
发掘出来后被copy成了电子版，现在要你分析哪个版本是原版。甚至有可能，有两三个
原版。现在把信息量最大（29903字母）发掘时间比较靠前的文件（文件名Wuhan-HU1/ |
f********1
发帖数: 1601 | 32 比较应该就是普通文本比较里用的longest Common subsequence算法吧。树里每个节点
就是和母节点最小的样本。 |
c*********n
发帖数: 1282 | 33 看来弦月不转码工屈才了。有能力这么描述这个问题，应该可以转码。 |
S*******l
发帖数: 4637 | 34 这就是经典文本批判问题(textual criticism).
一个例子就是圣经文本批判，通过各种抄本的区别，判断谁先谁后承继问题。
29903
【在 x********e 的大作中提到】
: 你有100多份文件（并且将来还会不断有新文件传给你）。每份文件的内容大概在29903
: 字母（目前的最大文件）到29840字母之间。每个字节只可能是A，T，C，G四个字母之
: 一，比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本，有
: 各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被发
: 掘出来后被copy成了电子版，现在要你分析哪个版本是原版。甚至有可能，有两三个原
: 版。现在把信息量最大（29903字母）发掘时间比较靠前的文件（文件名Wuhan-HU1/
: 2019）作为原始版作为root of the tree。要求你设计一个算法，把其他文件根据相似
: 度做一个树。
: 先看多少人有思路吧，之后我在细化加大难度。
|
l*******k
发帖数: 922 | 35 生物信息的情况要复杂得多。很多情况下突变几率是不相同的，比如a变成g的几率大于
变成u或者c.因为RNA只有四种nucleotide,还经常会发生变过去又变回来的情况。
【在 S*******l 的大作中提到】
: 这就是经典文本批判问题(textual criticism).
: 一个例子就是圣经文本批判，通过各种抄本的区别，判断谁先谁后承继问题。
:
: 29903
|
S*******l
发帖数: 4637 | 36 就是简化一下让lay people明白在讨论什么性质的问题。
【在 l*******k 的大作中提到】
: 生物信息的情况要复杂得多。很多情况下突变几率是不相同的，比如a变成g的几率大于
: 变成u或者c.因为RNA只有四种nucleotide,还经常会发生变过去又变回来的情况。
|
x********e
发帖数: 35261 | 37 其实我已经有一个大概思路了，这个树不需要用很复杂的算法，python实现应该最快。
直接用find做序列比对，先整体，比对不上再break up。我python操作还是不够熟悉也
没时间，要谁熟悉python愿意跟我一起试试我的算法私信我吧
【在 c*********n 的大作中提到】
: 看来弦月不转码工屈才了。有能力这么描述这个问题，应该可以转码。
|
x********e
发帖数: 35261 | 38 我仔细想了一下滑窗是很经典的序列比对方式。但用在这个数据库里效率太低。这个数
据库有>99%的相似度，不应该从局部开始比对
【在 l******t 的大作中提到】
:
: 开不同尺度的滑动窗口一小块一小块的比
|
l*******k
发帖数: 922 | 39 没那么简单。如果仅仅是置换当然简单，但难点在有insertion/deletion。如果多了/
少了一两个，你就要猜了。
【在 x********e 的大作中提到】
: 其实我已经有一个大概思路了，这个树不需要用很复杂的算法，python实现应该最快。
: 直接用find做序列比对，先整体，比对不上再break up。我python操作还是不够熟悉也
: 没时间，要谁熟悉python愿意跟我一起试试我的算法私信我吧
|
x********e
发帖数: 35261 | 40 对，门外汉想凑热闹只能这么跟他们说。实际上更复杂，得手把手有思路了后再慢慢加
大难度和细节。
【在 S*******l 的大作中提到】
: 就是简化一下让lay people明白在讨论什么性质的问题。
|
|
|
x********e
发帖数: 35261 | 41 目前就你跟得上思路。所以我的算法第二步就是根据query跟subject（wuhan-hu1/2019
）的比对结果，输出几个数据到两个dictionary里。一个是insertion/deletoon
dictionary，一个是mutation dictionary。建树是根据两个dictionary来建。再复杂
一点可以自己定义class。
【在 l*******k 的大作中提到】
: 没那么简单。如果仅仅是置换当然简单，但难点在有insertion/deletion。如果多了/
: 少了一两个，你就要猜了。
|
C**********e
发帖数: 23303 | 42 这个要用hash字典记录所有的独特序列点，位置和发生在那个样本上，一定同时用
resize sliding Windows在所有样本同时比，最后hash表里独特序列最少的就是母本。
不敢说完全正确。 |
k****w
发帖数: 3753 | 43 Printed的方法就可以了，用dynamic programming算pair文件间的minimum edit
distance，然后拿minimum spanning tree |
T*******x
发帖数: 8565 | 44 有道理。
【在 C**********e 的大作中提到】
: 这个要用hash字典记录所有的独特序列点，位置和发生在那个样本上，一定同时用
: resize sliding Windows在所有样本同时比，最后hash表里独特序列最少的就是母本。
: 不敢说完全正确。
|
k****w
发帖数: 3753 | 45 原版的定义你没有，如果minimum weight树杈最多的不一定是原版，可能是变异的话，
你怎么定义原版？ |
n********g
发帖数: 6504 | 46 你这个很简单，也不需要假定哪一个版本是最初版。1990年代初的时候我就写过，用来
自动分析故意被感染计算机病毒的EXE/COM文件。字节长度也大得多。
我给你的建议是不要再跟这个问题。有能力做这种自动分析的没有几十万也有几万人。
早就应该有人分析出来了只不过不吭声。这不是什么技术问题，而是政治问题。这也是
后来我的教授们给我的建议。
不要做有用的人。别人聪明得很，你装糊涂，日子会过得comfortable。不然即使是蓝
皮，也难保有人往你怀里塞本红皮让你去中国自首。
【在 x********e 的大作中提到】
: 这个确实很关键，也涉及到生物学细节。我们先简单假定Wuhan-HU1/2019就是最早期版
: 本。其他细节等建树以后我们再fine tune。目前中国和GISAID的都是建好树了，但是
: 缺少fine tune，我现在的工作就是手工fine tune树的细节
|
C**********e
发帖数: 23303 | 47 想了一下最小距离 恐怕不合适
因为数据连续 没有固定的DNA词汇表
没有原本
所以和经典圣经问题不全一样 |
x********e
发帖数: 35261 | 48 hash只是生成方式。实际上这个字典entries应该包括突变位点对应subject的index，
该index突变成对应值需要多少entropy（“抄错”的难度），该index突变成对应值的
event数(几个手抄本出现这个错误），该突变是否造成了错义突变(抄错是否改变读者
对内容的理解）。最后是根据突变的频率，难度，和错误严重程度来建树。
【在 C**********e 的大作中提到】
: 这个要用hash字典记录所有的独特序列点，位置和发生在那个样本上，一定同时用
: resize sliding Windows在所有样本同时比，最后hash表里独特序列最少的就是母本。
: 不敢说完全正确。
|
x********e
发帖数: 35261 | 49 你就当这题是个brain teaser吧
【在 n********g 的大作中提到】
: 你这个很简单，也不需要假定哪一个版本是最初版。1990年代初的时候我就写过，用来
: 自动分析故意被感染计算机病毒的EXE/COM文件。字节长度也大得多。
: 我给你的建议是不要再跟这个问题。有能力做这种自动分析的没有几十万也有几万人。
: 早就应该有人分析出来了只不过不吭声。这不是什么技术问题，而是政治问题。这也是
: 后来我的教授们给我的建议。
: 不要做有用的人。别人聪明得很，你装糊涂，日子会过得comfortable。不然即使是蓝
: 皮，也难保有人往你怀里塞本红皮让你去中国自首。
|
C**********e
发帖数: 23303 | 50 听起来你的问题已经解决了
不错
: hash只是生成方式。实际上这个字典entries应该包括突变位点对应subject的
index，
: 该index突变成对应值需要多少entropy（“抄错”的难度），该index突变成对
应值的
: event数(几个手抄本出现这个错误），该突变是否造成了错义突变(抄错是否改
变读者
: 对内容的理解）。最后是根据突变的频率，难度，和错误严重程度来建树。
【在 x********e 的大作中提到】
: 你就当这题是个brain teaser吧
|
|
|
k*****k
发帖数: 1 | 51 灌装病毒问题写程序是舍近求远
灌装病毒总共出来不到半年，变异也没多少，手画都能看出来
没事就想写程序，也不动动脑子需要吗 |
T*******x
发帖数: 8565 | 52 假设100个总样品，所有样本头和尾都可以对齐，假设其中98个样品在x位置处有A，另
外两个在该处为G。怎么确认A是突变的还是G是突变的？
【在 x********e 的大作中提到】
: hash只是生成方式。实际上这个字典entries应该包括突变位点对应subject的index，
: 该index突变成对应值需要多少entropy（“抄错”的难度），该index突变成对应值的
: event数(几个手抄本出现这个错误），该突变是否造成了错义突变(抄错是否改变读者
: 对内容的理解）。最后是根据突变的频率，难度，和错误严重程度来建树。
|
C*********e
发帖数: 1 | 53 洗脚姐，看来真是伪码工，什么干货也没给，你是怎么进的google
【在 s*****r 的大作中提到】
: online testing，要在你痛恨的美国找工吗
|
T*******x
发帖数: 8565 | 54 算是能算出来，但是结果的物理意义不清楚啊。
【在 k****w 的大作中提到】
: Printed的方法就可以了，用dynamic programming算pair文件间的minimum edit
: distance，然后拿minimum spanning tree
|
x********e
发帖数: 35261 | 55 你的假设就错了。为啥头尾就一定能对齐？我出题的时候都告诉你文件大小在一个范围
之内。读题不仔细，扣分
【在 T*******x 的大作中提到】
: 假设100个总样品，所有样本头和尾都可以对齐，假设其中98个样品在x位置处有A，另
: 外两个在该处为G。怎么确认A是突变的还是G是突变的？
|
x********e
发帖数: 35261 | 56 但是我python实际操作不行，要找个熟练公写代码跑一下，把树建出来再验证。
【在 C**********e 的大作中提到】
: 听起来你的问题已经解决了
: 不错
:
:
: hash只是生成方式。实际上这个字典entries应该包括突变位点对应subject的
: index，
:
: 该index突变成对应值需要多少entropy（“抄错”的难度），该index突变成对
: 应值的
:
: event数(几个手抄本出现这个错误），该突变是否造成了错义突变(抄错是否改
: 变读者
:
: 对内容的理解）。最后是根据突变的频率，难度，和错误严重程度来建树。
|
S*******l
发帖数: 4637 | 57 再提供一个考虑，可以减少点复杂性。好比同一个弹坑两次着弹的几率可以忽略不记。
同一个碱基多次变异的几率也可以不用考虑。 |
k****w
发帖数: 3753 | 58 他的问题是按照相似度建树啊，minimum edit distance就是相似度最近的，minimum
weight树杈最多的就是原版
除非他重新定义相似度，give data meaning，不然string comparison不就是这个
[在 TheMatrix (TheMatrix) 的大作中提到：]
:算是能算出来，但是结果的物理意义不清楚啊。
:☆ 发自 iPhone 买买提 1.24.11 |
x********e
发帖数: 35261 | 59 因为码工本身不理解相似的生物学含义。他们算出来相似，但解释不了是什么相似。 |
T*******x
发帖数: 8565 | 60 是个数学问题，但是个open ended数学问题。
假设所有样本都可以对齐，给个坐标从1到30000。然后所有位置上多于一个变化的坐标
列出来，记为集合X，并记录其对应的变化的集合M_x，每一个x有一个集合。
函数空间，X到M，每一个x要映射到对应的M_x。每一个函数都可以作为祖先给出一个合
理发展树。然后标记每个发展树的概率...
【在 h*****s 的大作中提到】
: 这是一个数学问题
:
: ：你有100多份文件（并且将来还会不断有新文件传给你）。每份文件的内容大概在
: 29903字母（目前的最大文件）到29840字母之间。每个字节只可能是A，T，C，G四个字
: 母之
: ：一，比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本，
: 有各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被
: 发掘出来后被copy成了电子版，现在要你分析哪个版本是原版。甚至有可能，有两三个
: 原版。现在把信息量最大（29903字母）发掘时间比较靠前的文件（文件名Wuhan-HU1/
|
|
|
x********e
发帖数: 35261 | 61 不属实。突变有热点区。或者说，可能很多份手抄本都是由同一份父本来的，比如老师
布置作业让一堆学生都抄一份。目前统计最多的点突变有3份样品符合。这是建子树的
基础，很重要。
【在 S*******l 的大作中提到】
: 再提供一个考虑，可以减少点复杂性。好比同一个弹坑两次着弹的几率可以忽略不记。
: 同一个碱基多次变异的几率也可以不用考虑。
|
T*******x
发帖数: 8565 | 62 我知道，文件大小是在一个范围内，但是还是有头有尾啊。而且还能找到大量互相
match的片段作为对准依据。我假设头尾能对齐，不仅头尾能对齐，中间也有大量能对
齐。还得给出统一的坐标。这步算“预处理”。：）
【在 x********e 的大作中提到】
: 你的假设就错了。为啥头尾就一定能对齐？我出题的时候都告诉你文件大小在一个范围
: 之内。读题不仔细，扣分
|
T*******x
发帖数: 8565 | 63 对，这个表达为在祖先path上不能在一个点上多次变异。
【在 S*******l 的大作中提到】
: 再提供一个考虑，可以减少点复杂性。好比同一个弹坑两次着弹的几率可以忽略不记。
: 同一个碱基多次变异的几率也可以不用考虑。
|
s******n
发帖数: 3946 | |
F*******g
发帖数: 1 | 65 神马屄题？
日后再解！
29903
【在 x********e 的大作中提到】
: 你有100多份文件（并且将来还会不断有新文件传给你）。每份文件的内容大概在29903
: 字母（目前的最大文件）到29840字母之间。每个字节只可能是A，T，C，G四个字母之
: 一，比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本，有
: 各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被发
: 掘出来后被copy成了电子版，现在要你分析哪个版本是原版。甚至有可能，有两三个原
: 版。现在把信息量最大（29903字母）发掘时间比较靠前的文件（文件名Wuhan-HU1/
: 2019）作为原始版作为root of the tree。要求你设计一个算法，把其他文件根据相似
: 度做一个树。
: 先看多少人有思路吧，之后我在细化加大难度。
|
k****w
发帖数: 3753 | 66 一天能写完吗？我倒是在做跟covid-19有关的事，所以感兴趣 |
C**********e
发帖数: 23303 | 67 写这代码大概要一个小时呢
用hash的目的是保证独特序列统计在不同样本中出现次数和位置
前提条件是后代样本的某些独特序列不会突变回去母本 生物上有这个可能性吗？
如果生物有这个可能性 那么在数学上就不可能找到母本了
另外因为不知道特征序列到底有多长 所以使用可变滑动窗口可以提高效率
这些样本的数据量很小 所以不用考虑O(lgN)问题 O(N)就可以
【在 x********e 的大作中提到】
: 但是我python实际操作不行，要找个熟练公写代码跑一下，把树建出来再验证。
|
T*******x
发帖数: 8565 | 68 一个小时能写完？
【在 C**********e 的大作中提到】
: 写这代码大概要一个小时呢
: 用hash的目的是保证独特序列统计在不同样本中出现次数和位置
: 前提条件是后代样本的某些独特序列不会突变回去母本 生物上有这个可能性吗？
: 如果生物有这个可能性 那么在数学上就不可能找到母本了
: 另外因为不知道特征序列到底有多长 所以使用可变滑动窗口可以提高效率
: 这些样本的数据量很小 所以不用考虑O(lgN)问题 O(N)就可以
|
x********e
发帖数: 35261 | 69 这东西写出来以后会非常有用。特别是突发性流行病大数据研究方面，绝对牛逼。事实
上phylogenetic tree怎么算，要先考虑整个数据库的整体相似性。这个用目前的算法
可以给个百分比。如果相似度及其高（90%以上，且基因组小）用我的算法准确率远远
大于传统算法。传统算法是为差异度大的数据库设计的。
【在 C**********e 的大作中提到】
: 写这代码大概要一个小时呢
: 用hash的目的是保证独特序列统计在不同样本中出现次数和位置
: 前提条件是后代样本的某些独特序列不会突变回去母本 生物上有这个可能性吗？
: 如果生物有这个可能性 那么在数学上就不可能找到母本了
: 另外因为不知道特征序列到底有多长 所以使用可变滑动窗口可以提高效率
: 这些样本的数据量很小 所以不用考虑O(lgN)问题 O(N)就可以
|
I******i
发帖数: 203 | 70 感觉是个 unsupervised learning 问题，需要定义一下不同序列的距离（这个估计有
现成的算法），有了距离以后就可以调包了，Python有很多unsupervided learning包
，别的语言也有。比如 Hierarchical_clustering
https://en.m.wikipedia.org/wiki/Hierarchical_clustering，再比如k_means，em。
。。等算法
看看如何根据距离把它们clustering。
这种方法不需要根序列，只需要所有的序列以及如何计算各个序列之间的差异大小（距
离，或者什么别的score） |
|
|
C**********e
发帖数: 23303 | 71 不能用 unsupervised learning
无法采用类W2W距离算法
【在 I******i 的大作中提到】
: 感觉是个 unsupervised learning 问题，需要定义一下不同序列的距离（这个估计有
: 现成的算法），有了距离以后就可以调包了，Python有很多unsupervided learning包
: ，别的语言也有。比如 Hierarchical_clustering
: https://en.m.wikipedia.org/wiki/Hierarchical_clustering，再比如k_means，em。
: 。。等算法
: 看看如何根据距离把它们clustering。
: 这种方法不需要根序列，只需要所有的序列以及如何计算各个序列之间的差异大小（距
: 离，或者什么别的score）
|
r***n
发帖数: 3 | 72 有similarity matrix后就是个找minimum cost spanning tree
similarity matrix怎么定义就需要生物学知识了。。举个例子，可以基于Levenshtein
上加点heuristics |
r***n
发帖数: 3 | 73 formalize一点的话实际上应该有一个算突变概率的函数P, 进化路径是一条马尔科夫链 |
x********e
发帖数: 35261 | 74 你会python的话用class定义更方便。hashtable用来做基因组突变难度的reference
【在 C**********e 的大作中提到】
: 写这代码大概要一个小时呢
: 用hash的目的是保证独特序列统计在不同样本中出现次数和位置
: 前提条件是后代样本的某些独特序列不会突变回去母本 生物上有这个可能性吗？
: 如果生物有这个可能性 那么在数学上就不可能找到母本了
: 另外因为不知道特征序列到底有多长 所以使用可变滑动窗口可以提高效率
: 这些样本的数据量很小 所以不用考虑O(lgN)问题 O(N)就可以
|
x********e
发帖数: 35261 | 75 我手动算了一下，实际情况更加复杂，这个算法还要优化。如果是头上缺失或者中部的
插入/缺失，要用扣分方式排序加建子分支。另外，在发现gap（包括头部缺失），要在
其他文件里搜索该“特征”，做cluster。mismatch一般在0-6个之间，很难用来判断父
子关系，我大概会以减分的方式排序吧。
尾部的缺失要用加分的方式排序，权重要放得小一点。
【在 C**********e 的大作中提到】
: 写这代码大概要一个小时呢
: 用hash的目的是保证独特序列统计在不同样本中出现次数和位置
: 前提条件是后代样本的某些独特序列不会突变回去母本 生物上有这个可能性吗？
: 如果生物有这个可能性 那么在数学上就不可能找到母本了
: 另外因为不知道特征序列到底有多长 所以使用可变滑动窗口可以提高效率
: 这些样本的数据量很小 所以不用考虑O(lgN)问题 O(N)就可以
|
h*h
发帖数: 27852 | 76 这是字符串比较的问题，和发现文档的不同版本有哪些改变基本是一样的问题，具体算
法嘛，我不会，但是现在已经有现成的解决方案了。需要假设一个根，Wuhan-01比较合
理。
圣经手抄本更复杂一些，因为不能假设根，而是要找到根。
每个变化怎样数字化表达需要生物学知识。
怎样算是同一个树枝，也需要生物学知识。
这个问题还是很有价值的 |
n********t
发帖数: 21 | 77 有真实数据么? 可以跑出来看看结果
：你有100多份文件（并且将来还会不断有新文件传给你）。每份文件的内容大概在
29903字母（目前的最大文件）到29840字母之间。每个字节只可能是A，T，C，G四个字
母之
：一，比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本，
有各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被
发掘出来后被copy成了电子版，现在要你分析哪个版本是原版。甚至有可能，有两三个
原版。现在把信息量最大（29903字母）发掘时间比较靠前的文件（文件名Wuhan-HU1/ |
n********t
发帖数: 21 | 78 她学术水平搭不上cs ap 吧。要“牺牲”很大，人家才能帮她。
：
：找一个自己学校计算机系的感兴趣的助理教授合作好一些，自己只要是一作加通讯就
好了。 |
n*****9
发帖数: 654 | 79 听说过哈夫曼编码吗？
可以先搜索最长相似字段建字典库。然后用哈夫曼编码比较。
：) |
S******t
发帖数: 378 | 80 第一页已经给出标准的正确答案了，其他人都在胡说八道
稍微解释一下 100 c 2 大概是5000个边。
整个图每一个顶点就是一个基因编码文件，每个边将两个文件相连。
通过某种模型判断出两个文件距离是多少，记录在这个边上，比方说简单的模型可以是
最小编辑距离（即一个文件变成另一个文件最小改变数)。
接着只要求出整个图的最小生成树即可，complexity是 O(E*N^2) + O(ELogV)
E是文件对儿，也就是5000左右
N是每个文件大小
V是文件数量
【在 p*****d 的大作中提到】
: 对两两节点（文件）求edit distance作为两节点间的edge weight，从而构成一张无向
: 完全图G
: 然后对G求minimal spanning tree
:
: 29903
|
|
|
H**********e
发帖数: 1 | |
l*******k
发帖数: 922 | 82 你牛！每个序列3万个字母，你一个一个去比。
看完回复我充分理解了眼高手低这个词。 |
x********e
发帖数: 35261 | 83 所以我都懒得跟一些人争
【在 l*******k 的大作中提到】
: 你牛！每个序列3万个字母，你一个一个去比。
: 看完回复我充分理解了眼高手低这个词。
|
k********t
发帖数: 1 | 84 这些全世界各地上传的测序数据，都有不可避免的sequencing error，也是各种noise
，不能都认定为突变，除非特定突变在多个测序数据里稳定出现了。
【在 x********e 的大作中提到】
: 这个确实很关键，也涉及到生物学细节。我们先简单假定Wuhan-HU1/2019就是最早期版
: 本。其他细节等建树以后我们再fine tune。目前中国和GISAID的都是建好树了，但是
: 缺少fine tune，我现在的工作就是手工fine tune树的细节
|
Y**M
发帖数: 2315 | 85 无责任瞎给一个简便算法。
先假定长度一样，内部没有整段的错位，只有个别不同。
这个好算吧？
只要规定分数即可。如果有100份，在某一位置上，如果100都相同，就都得100分
（或都不得分）。如果99份相同，这99份都得99分，剩下1份得1分（等于扣了98分）。
这样算下来，分数最高的就是原件。
当然，也可以改变权重，例如，连错3个按错2个半扣分，等等。
对于错位、短缺或冗余，经过处理后，也可以使用上述原则。当然，最麻烦的就是
错位。只有出现在两端的，才单纯是短缺和冗余，短缺和冗余是错位的特例。
错位怎么处理？
就是识别片段。即哪些部分是长度不变的。可以规定一个分数范围，只要长度不变
，内容差不多的，都可以识别为片段。片段内部的差异可以直接算分。
注意：对于有些体系，识别片段必须预估错位程度。你不能把某一份的开头片段，
识别为和另一份的中间片段是一段，那就麻烦了，没法比较了（我的意思是说，我不打
算想算法了）。
我们必须假设，错位是有限度的，只比较接近位置以识别片段。
识别完片段。对于片段的短缺，和片段间的冗余，都可以分别算分。注意这个地方
，可能更需要改变权重，例如，增加三个，按错1个半扣分，之类。 |
T*******x
发帖数: 8565 | 86 看第一段算法大意，有一定合理性。
【在 Y**M 的大作中提到】
: 无责任瞎给一个简便算法。
: 先假定长度一样，内部没有整段的错位，只有个别不同。
: 这个好算吧？
: 只要规定分数即可。如果有100份，在某一位置上，如果100都相同，就都得100分
: （或都不得分）。如果99份相同，这99份都得99分，剩下1份得1分（等于扣了98分）。
: 这样算下来，分数最高的就是原件。
: 当然，也可以改变权重，例如，连错3个按错2个半扣分，等等。
: 对于错位、短缺或冗余，经过处理后，也可以使用上述原则。当然，最麻烦的就是
: 错位。只有出现在两端的，才单纯是短缺和冗余，短缺和冗余是错位的特例。
: 错位怎么处理？
|
T*******x
发帖数: 8565 | 87 我不是抬杠，minimum weight spanning tree，这个得到了。树杈多的是原版，这句话
能这么说吗？还是这是定论？
【在 k****w 的大作中提到】
: 他的问题是按照相似度建树啊，minimum edit distance就是相似度最近的，minimum
: weight树杈最多的就是原版
: 除非他重新定义相似度，give data meaning，不然string comparison不就是这个
: [在 TheMatrix (TheMatrix) 的大作中提到：]
: :算是能算出来，但是结果的物理意义不清楚啊。
: :☆ 发自 iPhone 买买提 1.24.11
|
T*******x
发帖数: 8565 | 88 标准正确答案？什么问题的标准正确答案啊？
【在 S******t 的大作中提到】
: 第一页已经给出标准的正确答案了，其他人都在胡说八道
: 稍微解释一下 100 c 2 大概是5000个边。
: 整个图每一个顶点就是一个基因编码文件，每个边将两个文件相连。
: 通过某种模型判断出两个文件距离是多少，记录在这个边上，比方说简单的模型可以是
: 最小编辑距离（即一个文件变成另一个文件最小改变数)。
: 接着只要求出整个图的最小生成树即可，complexity是 O(E*N^2) + O(ELogV)
: E是文件对儿，也就是5000左右
: N是每个文件大小
: V是文件数量
|
S*E
发帖数: 3662 | 89 计算每两个文件的距离，定义为从一个文件变成另一个文件需要的最少错误数。
然后找到这个图里的最小树。
再然后，如果你知道哪一个文件是原始文件，就可以得到所有文件的传承顺序。
29903
【在 x********e 的大作中提到】
: 你有100多份文件（并且将来还会不断有新文件传给你）。每份文件的内容大概在29903
: 字母（目前的最大文件）到29840字母之间。每个字节只可能是A，T，C，G四个字母之
: 一，比26个字母加数字符号简单多了吧。假设这些文件跟圣经一样是古老的手抄本，有
: 各种错抄漏抄甚至别有用心往里面夹带私货的可能性。这些“手抄本”在全国各地被发
: 掘出来后被copy成了电子版，现在要你分析哪个版本是原版。甚至有可能，有两三个原
: 版。现在把信息量最大（29903字母）发掘时间比较靠前的文件（文件名Wuhan-HU1/
: 2019）作为原始版作为root of the tree。要求你设计一个算法，把其他文件根据相似
: 度做一个树。
: 先看多少人有思路吧，之后我在细化加大难度。
|
T*******x
发帖数: 8565 | 90 哦，树根定在已知的原始文件上，纲举目张，有道理。那如果不知道原始文件而要找原
始文件，那就不行了，对吧？
【在 S*E 的大作中提到】
: 计算每两个文件的距离，定义为从一个文件变成另一个文件需要的最少错误数。
: 然后找到这个图里的最小树。
: 再然后，如果你知道哪一个文件是原始文件，就可以得到所有文件的传承顺序。
:
: 29903
|
|
|
S*E
发帖数: 3662 | 91 可以寻找使得树的深度最小的根。
【在 T*******x 的大作中提到】
: 哦，树根定在已知的原始文件上，纲举目张，有道理。那如果不知道原始文件而要找原
: 始文件，那就不行了，对吧？
|
k****w
发帖数: 3753 | 92 找root node可以用leader election，这个算法自己定义
譬如选择weight为0的几个文件，也就是相同的文件最多的当leader，etc
这个问题没有讨论下去的必要了，浪费时间，楼主显然把这个版当成生物版了
[在 TheMatrix (TheMatrix) 的大作中提到：]
:我不是抬杠，minimum weight spanning tree，这个得到了。树杈多的是原版，这句
话能这么说吗？还是这是定论？
:☆ 发自 iPhone 买买提 1.24.11 |
T*******x
发帖数: 8565 | 93 嗯，deterministic. 其合理性可能还需要讨论。
【在 S*E 的大作中提到】
: 可以寻找使得树的深度最小的根。
|
T*******x
发帖数: 8565 | 94 Deterministic. 不错，谢谢。
【在 k****w 的大作中提到】
: 找root node可以用leader election，这个算法自己定义
: 譬如选择weight为0的几个文件，也就是相同的文件最多的当leader，etc
: 这个问题没有讨论下去的必要了，浪费时间，楼主显然把这个版当成生物版了
: [在 TheMatrix (TheMatrix) 的大作中提到：]
: :我不是抬杠，minimum weight spanning tree，这个得到了。树杈多的是原版，这句
: 话能这么说吗？还是这是定论？
: :☆ 发自 iPhone 买买提 1.24.11
|
