一、总体分析
1、前期思考
交叉点——计算生物学中的大规模计算及算法与高性能计算结合；重点基础还是掌握高性能计算方法，在这个基础上进行具体算法的适配与实践；人工智能赋能生物计算的今天，这些老的方法的作用和地位如何，最终研究加速ai+生物计算算法？
硬件系统
数据流（依赖网上数据库）：基因测序仪产生输入（FASTQ文件）；输出（VCF文件）；中间数据（BAM文件）
function：基因分析——比对排序去重比对
当前主流基因组分析流程（几个步骤：Base-calling、Quality Control、Pre-Alignment
Filtering、Read Mapping、Variant Calling）；
方法一：实现一个完善的SoC【硬】，完全运行自定义指令集
方法二——选用核（香山core）加专用加速部分【硬设计】，首先把香山core及上面的linux跑起来【软熟悉】，再编写自定义指令并执行（参考异构操作的方法，或调用显卡的方法）
软件系统
方法一：裸机程序或简单操作系统——IO系统操作与显示（按钮、OLED屏）
方法二：linux——命令行操作与显示（键盘、显示器）
问题
完全熟悉基因分析流程、算法及实例
FPGA目前还在家
2、立项分析
现状
处理大规模基因组数据集，测序数据的分析 速度远落后于数据生成速度
当前基于CPU或异构计算的基因分析工作流存在设备成本高昂、计算资源利 用率低、数据存储与传输瓶颈、长读段实时处理困难等问题
实际应用
序列比对、变异检测及复杂生物信息学分析
公共卫生事件时，需要在最短时间内处理大量样本并识别病原体，提供基因分析结果，追踪病毒的传播路径和变异情况；肿瘤精准治疗
市场解决方案
基于CPU和GPU加速的解决方案，拆解计算任务，提高并行度；效果30h->30min
计算：CPU+Sentieon软件 和 Nvidia GPU+Parabrics软件
存储：全本地、全外置（相对稍快）、混合式（最佳选择）
戴尔科技解决方案
高性能分布式共享存储采用戴尔分布式横向扩展存储PowerScale，主要缓存基因测序仪输出的海量待分析数据和二级、三级分析结果数据，并为二、三级分析提供高速IO读写支持和数据共享支持。
普通算力集群采用戴尔PowerEdge C系列刀片服务器，主要进行外显子测序(WES)，转录组测序(RNA-Seq)，蛋白结合位点分析(ChIP-Seq)等分析工作，这些工作对算力和内存的需求相对较低，建议配置Intel 5系CPU，256GB以上内存，采用2块1.92TB NVME硬盘存储参考基因组文件，二级分析时产生的临时文件等。
高性能算力集群采用戴尔PowerEdge R750机架式服务器，主要进行全基因组测序(WGS)，靶向测序(Panel)等，这些分析工作对算力和内存要求都非常高，建议配置Intel 8系CPU，1TB以上内存，采用4块1.92TB NVME硬盘存储参考基因组文件，二级分析时产生的临时文件等。并可根据二、三级分析加速需求，AI建模/推理需求等选配GPU加速卡。
四代基因测序的对比
测序技术 第一代 第二代 第三代 第四代 代表性测序平台 ABI3730XL IlluminaHiSeqX LifeTechPGM LifeTechPGM LifeTechSOLiDT Roche454FLX PacBioRS OxfordNanoporeMinION 原理 桑格双脱氧测序法 可逆链终止测序法 半导体测序法 半导体测序法 连接测序法 焦磷酸测序法 单分子实时测序 纳米孔测序法 测序长度 900bp 150bp2 200bp×2 400bp 50bp×2 1000bp 7000-8000bp 超过150k 通量 300Mb/年 219Tb/年 11Tb/年 1.4Tb/年 4.4Tb/年 180Gb/年 146Gb/年 9000-1800Gb/年 测序费用 107美元/Gb 7-10美元/Gb 80 美元/Gb 450美元/G 60 美元/Gb 160美元/Gb 2000美元/G 13美元/G 准确率 100% 99.80% 99% 99% >99.94% >99% 88% 99% 优点 测序长度长、准确率高 通量大、单位测序成本低 较长读长，成本中等，读取速度快，避免了 PCR 偏向性问题 极限读长，成本中等，实时监控测序，测序过程简单快捷，微量建库 缺点 通量低、成本高、测序结果存在偏好性 测序长度短导致序列拼接难度大、测序结果存在偏好性、测序过程繁琐 准确度低设备昂贵 准确度低，边缘点检测易出错误。
3、具体原理
算力＋存力：优化基因测序的关键所在 GenerationSequencing
一级分析：将需要进行测序的生物样本送入基因测序仪中，由测序仪进行WGS(全基因组测序)、WES(外显子测序)等测序操作，测序结果输出到可用于计算机进行分析的FASTQ文件中。FASTQ文件类似一个文本文件，每两行或三行记录一个DNA片段的碱基序列信息，测序质量信息等。 完整的DNA测序样本在进行测序前会被用超声波击碎为上千万条。
二级分析：这个过程现在通常由高性能处理集群完成。首先通过高性能服务器将测序仪生成的FASTQ文件(盗版书)与参考基因组文件(正版书)进行比对生成BAM文件。然后对BAM文件进行排序和去重，生成可以用于变异检测的BAM文件。
在最后，将BAM文件(有正确页号和行号的盗版书)与参考基因组文件(正版书)再次进行比对，找出BAM文件中所有与参考基因组文件不同之处，并将这些不同(变异)写入到VCF文件中。
三级分析：医学专家或科研人员通过分析服务器和专业数据库对VCF文件进行解读，给出疾病解读报告或者基因关联分析报告。疾病解读报告主要用于临床，比如某种基因突变是否可以使用某种靶向药物等。基因关联分析报告主要用于科学研究，比如某种基因突变会带来某种生理现象或者疾病等。
4、课题内容及目标
分析并针对基因分析工作流，分析并针对现有加速技术优化和缺陷（综述），基于FPGA提出新型专用体系结构（基础部件、可拓展性、技术算法通用性）
具体研究内容（具体见立项书）
- 工作流
- 定制化指令集架构
- 高效计算架构（异构；通用核加专用加速器；具体架构【流水线、任务并行调度、动态任务划分…】）
- 存储与通信结构（存储层次【缓存替换策略与预取机制】与片上互连【NOC、总线…】、）
- 原型验证设计实现（硬件设计、软件工具链【编译器、汇编器、调试器】、性能能效面积对比【与通用平台】）
目标
针对什么问题，搭建什么结构，实现什么软硬件，达到什么性能
拟解决的关键科学问题
针对各种算法的分析与专用指令集架构和计算结构的构建。实现过程中的技术细节和优化细节。
5、研究方案及可行性
把研究内容的点拆开讲即可；800字的自信宣言，讲团队的丰富经验和项目的技术可行性。
6、项目特色与创新之处
- 面向的是基因分析全流程（一体性）
- 负载特征驱动的定制化硬件设计（定制化）
- 高效并行与低功耗的专用计算架构 及 面向海量数据的高效存储与通信结构创新（性能功耗）
- 基于FPGA的可重构原型验证系统构建（平台优势）
二、相关资料
1、《生物信息学导论：面向高性能计算的算法与应用》
学科交叉，生物信息学和高性能计算相结合
相关基础问题的求解算法及原理实现——序列比对（算法、并行化方法）、蛋白质组分析（结构预测、质谱分析）、生物学网络分析（聚类）
全书架构：
一、分子生物学基础
印迹与杂交技术
DNA测序——链式终止法（chain-termination method）
现代分子生物学中经典计算问题——基因发现问题、序列对比问题、预测三维空间结构…
二、数学及计算科学基础
线性代数理论
n维欧氏空间Rn，C为全体复数集；共轭转置矩阵与转置矩阵；酋矩阵与正交矩阵（转置矩阵=逆矩阵）；矩阵范数；矩阵特征值与特征向量；矩阵的广义逆
概率论理论
随机事件（基本事件、全事件空间）
马尔科夫链——一个随机过程X，有限状态空间S{S1…Sn}、实践离散（0,1，…），具有无记忆性（下一状态只和当前状态有关）、时间齐次性（概率与t无关）
概率转移矩阵Px；吸收状态Si（进入后无法离开，因向其他部分转移的概率为0【矩阵乘】）、k步转移概率矩阵、相通与不可约（任意两个状态都相通）
一条马氏链可由其初始状态概率分布π=(π1,…πn)和状态转移矩阵完全刻画
状态Si在m步首次转移到Sj的概率fmij；迟早转移的概率fij；常返fii=1，返回的平均步数μii=Σm*fmij，零常返的；遍历的；平稳的
【……遇到不会的再回来看】
三、序列对比的基本方法
总结
利用动态规划技术
| 问题 | 算法 | 罚分模型 | 改进 |
|---|---|---|---|
| 局部比对问题 | Smith-Waterman算法 | 仿射空间罚分模型O(n^3) | 动态规划算法O(n^2) |
| 全局比对问题 | Neddleman-Wunsch算法 | 固定空位罚分模型O(n^2) | Huang X[144] O(n) |
9、 仿射空位罚分模型下的局部对比算法
10、降阶空间存储的两序列对比算法
一、线性空间复杂性算法
二、CheckPoint算法
映射到多处理器的并行计算系统
15、多序列比对
三、星形比对算法
四、序列比对的并行计算
五、基于字符串精确匹配的序列比较
六、基因识别
七、马氏链与隐马氏模型
2、Accelerating Genome Analysis: A Primer on an Ongoing Journey
基因组分析基本上是从一个已知的测序片段**比对定位（Read mapping）**过程开始的，在这个过程中，将生物基因组的测序片段与参考基因组进行比对（sequence alignment）。 瓶颈在于read mapping，如今基因测序比分析快得多。
read: small random fragments of an organism’s DNA sequence. (hundred to million bases)
baes: 碱基
文章分析read mapping的发展方向，展示高性能计算架构，即最先进的 1）算法 2）软硬件协同方式 3）硬件加速方法；展示结构是按照基因分析流程的三个步骤，针对每个步骤介绍加速方法。
基因组拼接（Genome assembly）是目前快速准确确定个体整个基因组的瓶颈（bottleneck），这是因为拼接需要复杂的算法和大量的数据集。
read mapping中read与reference genome比对的错误来源（测序错误、个体变异）；故使用近似字符串匹配算法ASM（approximate string matching），过去通常使用DP（dynamic programming，动态规划）算法作为软件在CPU上，占用了70%的处理时间[^1]，例如minimap2[^2]（一个read mapper）；并使用基因变异回溯（genomic variant calling）算法找到不同。
最先进的CPU上read mapper[^3]综述，问题：
- cpu和主存间数据传输；
- 测序和分析速度矛盾，相差几十倍；
- 增加CPU数提高速度就会提高功耗，且比对未知基因时依次比对的工作量更大，云计算对数据保护不友好。
READ MAPPING
找相似子序列（E edits，其中E是距离阈值edit distance threshold，为将一个序列转换为另一个序列所需的最小更改次数。 编辑操作包括删除、插入和替换一个或两个序列中的字符）；前置操作indexing and filtering以减少比对片段数
具体过程：1）划分Read和Reference Genome的 substrings (seeds，通过哈希索引或精确匹配算法（如k-mer匹配）找到的完全相同的短序列片段) 并索引编号（即图中k-mers，为长度为k的滑动窗口），定位相同片段 2）过滤器（pre-alignment filters）过滤不相似（超过E）的配对，减少序列比对算法使用次数 3）再次使用ASM进行比对，并使用DP算法寻找使比对分数（alignment score，自定义，基于the number of edits and/or matches）最大的前缀（prefixes）
输出结果到 sequence alignment/map (SAM) file
注：DP算法提供最精确值但时空复杂度为O(n^2)，n为序列长
ACCELERATING INDEXING
采用seed以避免对整个Genome使用ASM，只有read上的关联location才使用ASM。最大的挑战在于选择seed的长度和产生索引的数量。过短需要检查的location太多，太长匹配率下降。
加速方法：减少seeds数， 通过从基因组区域内的一组相邻种子中寻找最小代表性种子集合(称为最小化器，minimizers) 。可以通过强制排序来计算代表集（按字典顺序或哈希值）？并使用先进数据结构来索引（例如FM-index[^4]，全文索引的压缩表示和不解压下的查询（query）；优点：可查询任意长度种子、比minimap2的存储占用小1倍。但压缩导致定位速度较经典算法慢，改进——BWA-MEM2[^5]）
Reducing Data Movement During Indexing
RADAR[^6]存算一体ASIC
ACCELERATING PRE-ALIGNMENT FILTERING
根据E edits过滤， Pre-alignment filter 的四种主要方法： 1) the pigeonhole principle; 2) base counting; 3) q-gram filtering; or 4) sparse DP.
一般选用3)、4），其性能与read长度线性相关，且与edit distance无关
Pigeonhole Principle
长度为m的read， the read and reference segment are considered similar if they share at most E+1 nonoverlapping subsequences（differ by E edits）, with a total length of at least m-E.
Shouji‘s work[^1]（其他工作：SHD on FPGA、GenCache for cache）
base counting filter
根据各碱基总数过滤，差别大于E则过滤。
q-gram filtering
q-gram: all of the sequence’s possible overlapping（重叠的） substrings of length q【 例如，对于字符串
"hello"，它的 2-gram 有：he,el,ll,lo】m、E对共享q-gram数的影响：Given a sequence of length m, the minimum number of shared q-grams between two similar sequences is therefore [m-q+1, q*E] .
特性：对于e编辑敏感，将破坏多个q-gram（q-gram filtering is generally robust in handling only a small number of edits, as the presence of edits in any q-gram is significantly underestimated (e.g., counted as a single edit). ）
GRIM-Filter[^7]
sparse DP
仅在种子之间的间隙区域（非精确匹配区域）执行DP计算（种子本身是完全匹配的）
ACCELERATING SEQUENCE ALIGNMENT
长read对DP算法计算复杂度提升大，此时用到 Heuristic-Based Alignment Accelerators
Accurate Alignment Accelerators
Heuristic-Based Alignment Accelerators
[^1]:M. Alser, H. Hassan, A. Kumar, O. Mutlu, and C. Alkan, “Shouji: A fast and efficient pre-alignment filter for sequence alignment,” Bioinformatics, vol. 35, pp. 4255–4263, 2019. [^2]: H. Li, “Minimap2: Pairwise alignment for nucleotide sequences,” Bioinformatics, vol. 34, pp. 3094–3100, 2018. [^3]: M. Alser et al., “Technology dictates algorithms: Recent developments in read alignment”, 2020, arXiv:2003.00110. [^4]: R. Langarita et al., “Compressed sparse FM-index: Fast sequence alignment using large k-steps,” IEEE/ ACMTrans. Comput. Biol. Bioinformatics,tobe published, doi: 10.1109/TCBB.2020.3000253. [^5]:M. Vasimuddin, S. Misra, H. Li, and S. Aluru, “Efficient architecture-aware acceleration of BWA-MEM for multicore systems,” in Proc. IEEE Int. Parallel Distrib. Process. Symp., 2019, pp. 314–324. [^6]:W. Huangfu, S. Li, X. Hu, and Y. Xie, “RADAR: A 3D-ReRAMbasedDNA alignment accelerator architecture,” inProc.Des.Autom. Conf., 2018, pp. 1–6. [^7]:A. Goyal et al., “Ultra-fast next generation human genome sequencing data processing using DRAGENÒ Bio-IT processor for precision medicine,” Open J. Genetics, vol. 7, pp. 9–19, 2017.