Assembling large genomes with single-molecule sequencing and locality-sensitive hashing
好好读读，算法系列的好文章！
Assembling large genomes with single-molecule sequencing and locality-sensitive hashing - NATURE BIOTECHNOLOGY
marbl/MHAP - Github
MinHash Alignment Process (MHAP): a probabilistic sequence overlap algorithm. - ReadTheDocs
PacificBiosciences/blasr – Github
Frequently Asked Questions: Data File Formats
BLASR M4 format - MHAP的输出格式
摘要
单分子实时测序技术（SMRT）常被用于完成微生物基因组，但是可用的组装方法还没有规模化应用到大型基因组上。
我们引入了MinHash Alignment Process (MHAP)来比对高噪音、长的reads，使用概率学和locality-sensitive hashing。
集成了MHAP的Celera Assembler使得 reference-grade的de novo组装变为可能（…）。
组装的结果高度的连续，包含了染色体臂、close persistent gaps的完整解决方案。
我们的D. melanogaster组装结果揭示了先前未知的异染色质和端粒序列，也组装了低复杂性的CHM1，从而填补了人类GRCh38的gap。
使用MHAP、CA和SMRT可以denovo出近乎完整的真核基因组，准确率达到99.99%。
前言
The primary bottleneck of long-read assembly has been the sensitive all-versus-all alignment required to determine overlapping read pairs.
长reads组装的主要瓶颈是两两比对的敏感性，用于决定reads对的overlap。
本文提供了一种概率算法，可以高效地检测出高错误长reads之间的overlap。
MHAP uses a dimensionality reduction technique named MinHash to create a more compact representation of sequencing reads.
MHAP使用了MinHash 的降维技术来创建了测序reads的更加紧凑的表示形式。
MinHash 最初是开发用来检测不同网页之间的相似度，它将文本或字符串减少到了一系列的fingerprints，称为sketch。
结果
MinHash alignment filtering
MHAP overlapping performance
SMRT sequencing and assembly
De novo human assembly using long reads
Assembly validation and repeat resolution
Improved telomere assemblies
讨论
待续~