Introduction
Polyploidy 多倍体：是拥有多余两个同源染色体的基因组，人、土豆、小麦、草莓分别有2、4、6、8个同源染色体
haplotypes 单倍型：是指生物体的一条染色体上来自于某一单亲的一组紧密相连的等位基因组合。 每个人有两条单倍型，分别来自双亲
dosage 剂量：描述了多态性位点变异的频率
Ranbow 根据short reads 重建多倍体的单倍型，ranbow的设计考虑以下领域的见解（ We designed Ranbow to account for the following domain-specific insights:）：
两个比对的reads之间完全相同的overlap并不代表它们源于一个单倍型，并且可能不会被组装到一个单倍型
必须考虑观察到的大量多等位基因变异
需要考虑到不同形式的错误，包括源自碱基、变异、剂量信息、比对错误。
它利用高度杂合区域中 pair-end reads 中的密集变异来重建所有同源染色体的单倍型。它聚合reads，并在变异位点级别把它们组装成短的单倍型，通过多分图对区域进行单倍体拓展
Materials and methods
Ambiguity of Merging (AoM) 合并片段的歧义问题是多倍体单倍型重建的一个主要问题
Definitions and problem formulation
给定一个 P 倍体生物（P-ploid），一个单倍型定义为P个同源染色体中的一个染色体 上的变异序列。本文集中于单碱基替换、多碱基替换以及小（<50bp）插入和缺失而变化的位点，称为 Small Polymorphism (SmP)。这些变异编码成0 - P-1, 0代表参考等位基因，1代表第一个可选择的等位基因。把这个称为等位基因编码空间的单倍型 h_i^{coded\ allele\ space} = h_i =a[1].a[2].a[3] ... a[N] 这里 h_i 表示一个单倍型，a[n] 表示一个变异位点，N位点个数 .是序列连接点。F 称为所有片段 \{f_1, f_2, ...f_M\} 的集合， 一个片段f 是变异的序列，被一个比对的read覆盖的变异的序列。当一个read包含不在变异列表上的变异，这个位点称为 missing allele 或者 gap (-) 。两个片段之间的相似性和不相似定义为 sim(f_1,f_2) 和 dsm(f_1,f_2) 分别代表两个片段上相同变异位点的个数和不同变异位点的个数。定义单倍体段 haplotype segment s 为一个consensus 从一个片段集合 F' 中通过合并函数计算获得。 函数意义：找一个变异序列 s 使它和 F' 中所有片段的相同变异位点个数最多。 F' 作为 s 的支持片段集合。单倍型的重建目标是将片段 F 或者其子集组装成 P 个单倍型。
Short region haplotype reconstruction
一个mask(msk) 定义为SmP位点索引的有序集合。一个mask( t^{msk})的种子序列是mask索引处的一个比对的片段的序列模式。一个种子序列的支持片段( F_tmsk_j) 是一个在mask索引处带有相同变异的片段的集合，ranbow搜索具有足够多独立种子序列的的masks，每个种子序列集合了一组reads可以merge到一个单倍体段
Haplotype reconstruction on a mask
一个mask观察到的种子序列的数量(p) 和 P倍体的P比较有3种情况
p=P : 每个种子序列代表一个单倍体段，具有相似种子序列的片段来自一个单倍型。聚合这些片段， 作为种子序列的支持片段。ranbow merge 这些支持片段去构建单倍型段
t^{msk_j} 是一个种子序列， F_{t^{msk_j}}是支持片段集合， s^{msk_j}是一个组装的单倍型片段， b^{msk_j} 是获得的单倍型块（haplotype block）。
p>P : 在mask上有一个或者多个错误，在纠错步骤后保留P个种子序列。支持的种子序列越少，更有可能被认为是错误的种子序列，删除掉错误的种子序列，只保留P个种子序列。
p<P : 可以是由于其他错误，或者不同的同源染色体之间等位基因的相似性。
Elongating haplotype segments with flanking fragments
利用block内单倍型之间独特的匹配的overlap h_I \in b^{msk_j}和 相邻overlap片段 f_k延长单倍型。独特的匹配overlap有以下特点.
f_k和 h_I \in b^{msk_j}有匹配overlap说明 sim(f_k,h_I)>0\ and\ dsm(f_k,h_I)=0
f_k和 h_I \in b^{msk_j}有不匹配的overlap，说明 dsm(f_k,h_I)>0
如果 f_k 和 h_i \in b^{msk_j}中有一个有匹配overlap，和P-1个有不匹配overlap，说明 f_k 属于 h_I ，每轮迭代，ranbow选择一个单倍型和一个片段带有一个独特overlap，并合并它们，更新单倍型同时更新片段集合，迭代完后，ranbow使用同样的方法继续迭代新的单倍型和片段集合，
Detecting and evaluating all possible masks
获得带有所有种子序列和足够片段支持的所有mask，构建两层hash表，outer hash table (OHT) 和 inner hash table (IHT) ,OHT key是mask索引，value是hash table，IHT key是种子序列，值是支持的片段。对所有mask排序，ranbow计算支持片段的数量记录p个最高的种子序列，根据这些mask构建单倍型
Haplotype elongation via long range connections
paired-end, Hi-C, or long read 信息连接不同的单倍型segment，把这个问题作为 带权重k分图G(V,E,w) 单倍型block作为节点，有两个blocks信息的fragment作为边。理想情况下，一个延长的单倍型segment对应到 desired path （无冲突的path） 。conflicting path 是连接同一分区的两个节点的路径。 desired cycle 当两条路径连接来自不同单倍型块的两个节点时，我们将所需路径的定义扩展到所需循环。感觉意思是连接两个节点之间有两个不同的路径，可以形成一个循环。ranbow基于开始位置对单倍型block排序，从这个开始位置使用滑动窗口，在滑动窗口内查找cycle。在一个滑动窗口内构建部分图，ranbow搜书长度是3的循环，查找从a开始，到b,c 结束的两条路径，b c是不同节点，然后查找bc之间有没有路径，如果有构成一个triangles，找一个权（w(a,b)+w(a,c)+w(b,c)）重最大的triangles 。然后是通过直接连接拓展，对所有边降序排序，每次选择一个边，然后看合并后是否冲突，不冲突，合并成一个节点，更新图，
Phasing the regions with fewer than P unique haplotypes
ranbow可能会重建P个haplotype