CN116134525A

CN116134525A - 软件加速基因组读段映射

Info

Publication number: CN116134525A
Application number: CN202180039661.3A
Authority: CN
Inventors: G·A·P·里兹克
Original assignee: Inmair Ltd
Current assignee: Inmair Ltd
Priority date: 2020-09-15
Filing date: 2021-09-15
Publication date: 2023-05-16
Also published as: US20220084625A1; IL298979A; JP2023541090A; MX2022016018A; US11521707B2; ZA202304378B; EP4214713A1; US20230084414A1; BR112022024127A2; EP4654207A2; IL298979B1; IL298979B2; EP4214713B1; CA3174066A1; WO2022060910A1; IL316046A; AU2021344965A1; KR20230069046A; EP4214713C0

Abstract

公开了用于软件加速基因组数据读段映射的方法、系统、装置和计算机程序。在一个方面，该方法可包括以下动作：从基因组数据读段获得k聚体种子；基于所获得的k聚体种子生成基因组签名；使用散列数据结构确定与该k聚体种子的至少一部分匹配的参考序列位置，其中该散列数据结构包括N个数据单元，这些数据单元包括第一部分和第二部分，该第一部分存储预先确定的基因组签名，该第二部分存储与同该预先确定的基因组签名所来源于的k聚体种子的至少一部分匹配的参考序列位置的第一次出现相对应的值；以及基于一个或多个比对分数选择所确定的参考序列位置作为所获得的k聚体种子的实际比对。

Description

软件加速基因组读段映射

背景技术

本申请要求2020年9月15日提交的美国申请序列号63/078,890的权益，该申请全文以引用方式并入。

背景技术

在一些情况下，基因组读段映射描述识别基因的基因座和基因之间的距离的方法。计算机可用于分析一组或多组基因组数据并将分子标志物的集合(诸如一连串核苷酸)与分子标志物在给定参考基因组上的相应位置相关联。以此方式，计算机可用于将分子标志物的集合“映射”到参考基因组上。

发明内容

本公开涉及用于软件加速基因组读段映射的方法、系统和计算机程序。在一个方面，本公开涉及有利于软件加速基因组读段映射的散列表的生成。该散列表可包括表示使用基因组数据签名索引的参考基因组的数据。在一些具体实施中，所生成的散列表可用于确定所接收的基因组读段和参考基因组之间的映射。

根据本公开的一个创新方面，公开了一种用于软件加速基因组数据读段映射的方法。在一个方面，该方法可包括以下动作：由一个或多个计算机从基因组数据读段获得k聚体种子；由一个或多个计算机基于所获得的k聚体种子生成基因组签名；由一个或多个计算机使用散列数据结构确定与该k聚体种子的至少一部分匹配的参考序列位置，其中该散列数据结构包括N个数据单元，这些数据单元包括第一部分和第二部分，该第一部分存储预先确定的基因组签名，该第二部分存储与同该预先确定的基因组签名所来源于的k聚体种子的至少一部分匹配的参考序列位置的第一次出现相对应的值；以及由一个或多个计算机基于一个或多个比对分数选择所确定的参考序列位置作为所获得的k聚体种子的实际比对。

其他版本包括已经被配置为执行前述方法的动作的对应系统、装置和计算机程序。

这些和其他版本可任选地包括以下特征中的一个或多个特征。例如，在一些具体实施中，该预先确定的基因组签名可仅占用一个存储器存储字节。

在一些具体实施中，该值可仅占用四个存储器存储字节。

在一些具体实施中，该散列数据结构是具有N个数据单元的单个数组。

在一些具体实施中，该方法还可包括：由一个或多个计算机基于与该基因组数据读段的一个或多个k聚体种子相对应的第一值集过滤该基因组数据读段。

在一些具体实施中，该第一值集可包括应用于该基因组数据读段的该一个或多个k聚体种子的预先确定的操作的结果，并且其中该第一值集用于从该基因组数据读段获得该k聚体种子。

在一些具体实施中，该预先确定的操作可包括该基于基因组数据读段的该一个或多个k聚体种子和散列函数生成散列值。

在一些具体实施中，确定该参考序列位置可包括：由一个或多个计算机计算该基因组数据读段的该k聚体种子的第一位置，其中该第一位置对应于该k聚体种子在该基因组数据读段内的位置；以及计算该k聚体种子的第二位置，其中该第二位置对应于该k聚体种子在该参考基因组数据内的位置，并且其中该第二位置是基于该散列数据结构计算的。

在一些具体实施中，该方法还可包括：由一个或多个计算机基于该散列数据结构和该基因组数据读段对该一个或多个参考序列位置进行排序。

在一些具体实施中，该方法还可包括：由一个或多个计算机基于对该一个或多个参考序列位置进行排序来生成该一个或多个比对分数。

在一些具体实施中，该方法还可包括：选择所确定的参考序列位置中的至少一个参考序列位置作为所获得的k聚体种子的该实际比对包括：将该一个或多个比对分数与阈限值进行比较。

在一些具体实施中，该方法还可包括：该一个或多个比对分数包括表示来自该基因组数据读段的所获得的k聚体种子和该参考序列位置之间的不匹配的数量的数值。

在一些具体实施中，丢弃在与该预先确定的基因组签名所来源于的该k聚体种子的至少一部分匹配的参考序列位置的第一次出现之后的每次后续出现。

根据本公开的另一创新方面，公开了一种用于生成用于软件加速基因组数据读段映射的散列表的方法。在一个方面，该方法可包括：由一个或多个计算机接收基因组数据，其中该基因组数据来源于亲本基因组数据；由一个或多个计算机基于该基因组数据生成第一值集；由一个或多个计算机基于该第一值集生成该基因组数据的子集；由一个或多个计算机计算该基因组数据的该子集中的每个k聚体的签名，其中该签名是基于第一散列函数计算的；由一个或多个计算机计算该基因组数据的该子集中的每个k聚体的第一属性，其中该第一属性包括该基因组数据的给定k聚体在该基因组数据的序列内的位置；由一个或多个计算机计算该基因组数据的该子集中的每个k聚体的索引，其中该索引是基于第二散列函数计算的；以及由一个或多个计算机基于该基因组数据的该子集中的每个k聚体的该索引将该基因组数据的该子集中的每个k聚体的该签名和该第一属性存储在散列数据结构内。

这些和其他版本可任选地包括以下特征中的一个或多个特征。例如，在一些具体实施中，该基因组数据的该子集中的每个k聚体是包括表示一串一个或多个核苷酸的k个字母的k聚体。

在一些具体实施中，该第一值集可包括该基因组数据的给定k聚体在该亲本基因组数据内出现的次数的表示。

在一些具体实施中，该第一值集包括基于该基因组数据的对应k聚体计算的散列值的表示。

在一些具体实施中，用于存储该子集中的给定k聚体的签名的存储器分配大小小于用于存储该给定k聚体的存储器分配大小。

在一些具体实施中，该方法还可包括：由一个或多个计算机将对应于该散列数据结构的数据作为数据包发送到第一设备。

在一些具体实施中，该第一设备是存储器存储设备。

在一些具体实施中，第二设备从第一设备读取对应于该散列数据结构的该数据。在此类具体实施中，该第二设备可执行一连串操作以基于对应于该散列数据结构的该数据生成第二散列数据结构。

如本文所用的种子通常是指从基因组数据读段识别、获得或提取的一连串碱基调用或核苷酸。

k聚体(在本文中也称为k聚体种子)是元素(诸如碱基调用或核苷酸)的序列，其中给定k聚体的序列中的元素(例如，碱基调用或核苷酸)的数量由“k”定义。

基因组数据读段通常包括由核酸测序仪生成的数据，该数据对应于由该核酸测序仪测序的样品基因组的一部分的碱基调用或核苷酸。

基因组签名(在本文中也称为签名)是或包括识别散列表位置(例如，桶、时隙或单元)的数据。这种数据也可称为散列键，例如，基因组散列键。如果签名是从识别基因组数据的位置生成或指向该位置，则该签名是基因组签名。

参考序列位置是指参考序列(例如，参考核酸序列)的特定位点或部分。

散列数据结构以关联方式存储数据，并且可包括使用散列函数将散列键映射到存储器位置、桶或单元的数据结构。

比对分数是或包括指示映射到特定参考序列的基因组数据读段或k聚体种子实际上对应于该特定参考序列位置的置信度水平的数据。

基因组数据可包括与受试者(例如，人类受试者)的基因组相关的任何数据。

亲本基因组数据可包括从其提取基因组数据的子集的基因组数据的任何超集。例如，基因组数据读段可以是可从其提取k聚体种子的亲本基因组的示例。

“基于”特定基因组数据的值是来源于该基因组数据的值。

当使用多个散列函数时，第一散列函数可包括散列函数的初次出现。术语第一散列函数的使用并不意味着第一散列函数不同于所使用的任何后续散列函数，但可不同。

索引是可用于识别其他数据的存储位置的任何数据。

当使用多个散列函数时，第二散列函数可包括散列函数的后续出现。术语第二散列函数的使用并不意味着第二散列函数不同于先前使用的任何先前散列函数，但可不同。

如本文所述的所生成的散列表及其使用可提供多个技术益处。技术益处可包括与常规方法相比更快且需要更少存储器和存储要求的软件加速基因组读段映射算法。这些益处可至少部分地基于将基因组读段编码成一字节基因组数据签名以用作散列键以及使用单个数组散列表来实现。这些益处可至少部分地基于将基因组读段编码成一字节基因组数据签名以用作散列键以及使用单个数组散列表来实现。

除非另有定义，否则本文所用的所有技术和科学术语的含义与本发明所属领域的普通技术人员通常理解的含义相同。虽然与本文所述的方法和材料类似或等同的方法和材料也可用于本发明的实践或测试，但合适的方法和材料如下所述。本文提及的所有出版物、专利申请、专利和其他参考文献均全文以引用方式并入本文。如发生矛盾，以本说明书及其所包括的定义为准。此外，所述材料、方法和示例仅为例示性的，并非旨在进行限制。

本发明的一个或多个实施方案的细节在附图和下文的描述中进行阐述。根据描述、附图和权利要求，本发明的其他特征和优点将显而易见。

附图说明

图1是示出了用于生成用于软件加速基因组读段映射的散列表的系统的示例的图。

图2是示出了用于生成用于软件加速基因组读段映射的散列表的过程的示例的流程图。

图3是示出了使用用于软件加速基因组读段映射的散列表的系统的示例的图。

图4是示出了用于生成用于软件加速基因组读段映射的散列表的过程的示例的流程图。

图5是可用于实施用于生成用于软件加速基因组读段映射的散列表的系统和用于生成用于软件加速基因组读段映射的散列表的系统的计算机系统部件的图。

相同的参考标号和名称在各个附图中指示相同的元件。

具体实施方式

本公开涉及用于软件加速基因组读段映射的方法、系统和计算机程序。在一个方面，本公开涉及有利于软件加速基因组读段映射的散列表的生成。该散列表可包括表示使用基因组数据签名索引的参考基因组的数据。所生成的散列表然后可用于确定所接收的基因组读段和参考基因组之间的映射。所生成的散列表及其使用提供多个技术益处，包括与现有方法相比更快且需要更少存储器和存储要求的软件加速基因组读段映射算法。这些益处可至少部分地基于将基因组读段编码成一字节基因组数据签名以用作散列键以及使用单个数组散列表来实现。本公开的其他优点通过有助于减少考虑中的参考位置的数量的多个过滤阶段来实现。

在一些具体实施中，本公开的方面可用于改善基于参考的基因组数据压缩算法的性能。例如，本公开可在基于参考的fastq压缩内使用。然而，本公开不限于此。相反，软件加速基因组读段映射器可在多种其他操作中使用，诸如在生成经映射和比对的基因组读段以供输入到变体调用程序中期间或在生成经映射和比对的基因组读段以供输入到三级分析的一个或多个阶段中期间。

在一些具体实施中，诸如在基于参考的压缩算法中使用期间，软件加速基因组读段映射器可被配置为有利于提高映射速度，但同时损害准确度水平。然而，在其他具体实施中，软件加速基因组读段映射器可被配置为以映射速度为代价提供更准确的映射。一般来讲，可基于如本文所述的给定具体实施更改或优化变量和其他参数，以提供更准确的结果或更快速地呈现结果。

在一些具体实施中，一个或多个过滤阶段可用于应用一种或多种不同类型的相应过滤器来生成将用于生成散列表的参考基因组数据的子集。可生成参考基因组数据的过滤后的子集以减少存储器使用并加速计算。然后，可将参考基因组数据的过滤后的子集存储在散列表中。

可使用计算机来实现软件加速基因组读段映射，该计算机接收基因组读段，并且然后查询所生成的散列表以找到参考基因组数据中对应于基因组读段的给定k聚体的位置。散列表有利于软件加速基因组读段映射，因为散列表被配置为(i)减少用于存储作为散列键的基因组签名的存储器和与基因组签名匹配的参考序列位置的对应单元或桶，并且(ii)使用单个数组进行结构化。本文所述的系统、方法和特征可用于至少部分地基于所生成的散列表确定一个或多个候选比对，并且处理这些候选比对以快速找到满足给定标准的比对。

图1是示出了用于生成用于软件加速基因组读段映射的散列表的系统100的示例的图。系统100包括计算机106、散列操作模块108、出现计数器模块114和散列表生成模块120。计算机106被配置为向散列操作模块108、出现计数器模块114和散列表生成模块120提供数据并且从它们接收数据。在一些具体实施中，计算机106托管散列操作模块108、出现计数器模块114和散列表生成模块120中的一者或多者，使得可在计算机106上在本地处理一个或多个模块的处理操作。在其他具体实施中，散列操作模块108、出现计数器模块114和散列表生成模块120中的一者或多者可由连接到计算机106的一个或多个其他计算机托管。

散列操作模块108可生成对应于基因组数据的一个或多个散列值。在一些情况下，基因组数据可包括呈k聚体的形式的核苷酸序列。出现计数器模块114可对给定形式的基因组数据在该基因组数据所基于的亲本基因组数据内的出现次数进行计数。这是因为例如给定k聚体可在沿核苷酸的读段序列的多个位置处出现。由k聚体表示的一串连续核苷酸在核苷酸的读段序列内出现的次数可由出现计数器模块114获得。然后，散列表生成模块120可生成对应于由散列操作模块108和出现计数器模块114处理的基因组数据的散列表。下面以阶段A至阶段E的阶段描述图1的示例。

在本说明书中，给定k聚体定义为连续核苷酸的序列，其中给定k聚体的序列中的核苷酸数由“k”定义，并且核苷酸(或更一般地，碱基)由来自定义词汇表的字母串表示。例如，给定k聚体可表示序列“ATGCG”，其中符号：{A,C,G,T}表示存在于脱氧核糖核酸(DNA)中的四种类型的核苷酸，即腺嘌呤、胞嘧啶、鸟嘌呤和胸腺嘧啶。在核糖核酸(RNA)中，胸腺嘧啶被尿嘧啶(U)替代。

本公开中所提及的基因组数据可包括例如但不限于核苷酸序列、脱氧核糖核酸(DNA)序列或核糖核酸(RNA)。

在图1的示例的阶段A中，基于基因组数据102的k聚体集104被发送到计算机106。在此示例中，基因组数据102可包括参考基因组(其在本文中也可称为参考序列)，诸如由一个或多个科学家为生物体组装的DNA序列，并且k聚体集104中的每个k聚体对应于存在于基因组数据102中的具有核苷酸长度k的特定序列子集，其中k是大于0的任何正整数。例如，k聚体集104中的k聚体AAGT...AT对应于具有长度k核苷酸“AAGT...AT”的核苷酸序列的基因组数据读段或其一部分。基因组数据102包括k聚体AAGT...AT的至少一个实例，这意味着定义为对应于“AAGT...AT”的一串核苷酸的k聚体AAGT...AT的序列在对应于基因组数据102的核苷酸序列内出现至少一次。在一些具体实施中，参考序列由合成序列组成，该合成序列至少部分地被构思用于根据进一步处理来改善读段的可压缩性。

在一些具体实施中，k聚体集104内的k聚体可具有16个核苷酸的k聚体长度。然而，本公开不限于使用具有16个核苷酸的k聚体长度的k聚体的具体实施。一般来讲，任何数量的核苷酸都可用于k聚体集中的给定k聚体。在一些具体实施中，更短的种子在参考基因组上将具有更高的出现计数，并且可能导致更高的计算时间。短的种子还可能导致高灵敏度。与k聚体集104中的k聚体内的核苷酸数相对应的种子长度可出于诸如性能优化的优化目的进行调整。

计算机106接收k聚体集104。根据具体实施，计算机106可与一个或多个其他计算机通信以接收k聚体集104。例如，预处理计算机或其他设备可处理基因组数据102并且生成k聚体集104。然后，预处理计算机或其他设备可通过合适的通信网络与计算机106通信。其他设备的预处理计算机可将k聚体集104发送到计算机106。在一些具体实施中，计算机106执行预处理计算机或其他设备的操作。例如，计算机106可接收基因组数据102，并且基于基因组数据102生成k聚体集104。

在一些具体实施中，由计算机106接收的数据是非基因组数据的形式。例如，计算机106可接收信息。然后，可在一个或多个阶段中处理该信息。在一些情况下，信息可由诸如散列操作模块108、出现计数器模块114或散列表生成模块120的一个或多个模块处理。

在一些具体实施中，与由计算机106接收的信息相关的数据用于更改一个或多个处理操作。例如，所接收信息可用于更改计算机106的诸如散列操作模块108、出现计数器模块114或散列表生成模块120的任何操作模块的操作。例如，计算机106可接收信息。计算机106可从所接收信息提取一个或多个项。计算机106可基于所提取的一个或多个项确定要应用于所接收信息的特定处理方法。在一些情况下，该特定处理方法可包括一个或多个处理模块，其中该一个或多个处理模块用参数改变或操作改变调整，以基于所提取的一个或多个项以特定方式处理数据。

例如，在生成与基因组数据相关的散列表时，计算机106可接收基因组数据。计算机106可从所接收的基因组数据提取一个或多个项(例如，特定长度ki的一个或多个k聚体)。然后，计算机106可基于所提取的数据更改一个或多个模块的操作方法。例如，计算机106可通过改变表示指示k聚体中的碱基调用或核苷酸的数量的整数k的阈限值来更改出现计数器模块114。可将不满足由计算机106设定的阈限值的项滤除。

在一些具体实施中，k聚体集104可包括多个k聚体核酸序列，每个序列具有长度k，这些序列来源于可包括参考序列的基因组数据102。在一些具体实施中，计算机106可经由直接连接(例如，USB连接、USB-C连接等)或经由一个或多个网络连接(例如，LAN、WAN、以太网、WiFi、蜂窝网络、互联网等)接收k聚体集104。在一些具体实施中，计算机106可以是核酸测序设备，并且该核酸测序设备可接收、获得或以其他方式访问基因组数据102并且生成k聚体集104。

因此，在一些具体实施中，本公开的软件加速基因组映射和比对可在测序设备(诸如下一代DNA测序设备)上实施以执行二次分析操作，诸如在测序设备上映射和比对基因组数据读段。在其他具体实施中，本公开的软件加速基因组数据映射和比对可在除测序设备之外的另一计算机上实施，该另一计算机获得基因组数据，生成k聚体集104，并且使用k聚体集104或其一部分执行本文下文描述的其他操作中的一个或多个操作。

在阶段B中，散列操作模块108接收k聚体集104。图1所示示例的计算机106可通信地连接到散列操作模块108。散列操作模块108可基于k聚体集104执行一个或多个操作。例如，如图1所示，k聚体集104中的每个k聚体可用于生成对应的散列值。散列值可以是任何值。在图1的示例中，散列值被确定为介于0和2⁶⁴-1之间的值。

散列操作模块108可生成所计算的散列值112。所计算的散列值112可被处理，以便过滤所接收的k聚体集104。例如，散列操作模块108可使用所计算的散列值112来确定图1的示例所示的k聚体集104的子集作为第二k聚体集110。在一些具体实施中，第一过滤阶段可通过使用取模函数确定k聚体集104的子集来实施。在一些具体实施中，所计算的散列值112可由散列操作模块108与预先确定的映射相对应地生成。例如，如图1所示，映射可定义为：

公式1是散列操作模块108可用来计算一个或多个散列值的散列函数的示例。公式1描述k聚体集104中的给定k聚体到对应散列值的映射，在这种情况下，散列值是介于0和2⁶⁴-1之间的值，并且散列值可由64位无符号整数表示。在一些具体实施中，使用其他映射或散列函数，从而产生不同的散列值。例如，代替64位无符号整数，可使用32位带符号整数。本公开不限制散列函数模块108所使用的映射或散列函数的形式。在一些情况下，散列函数的类型可根据由计算机106接收的数据或由散列操作模块108接收的数据改变。

在处理k聚体集104时，图1的散列操作模块108可执行一个或多个操作。在一些具体实施中，该一个或多个操作可包括计算一个或多个值。在图1的示例中，散列操作模块108可计算k聚体集104中的每个k聚体的散列值。由散列操作模块108执行的散列值计算的示例在公式2中示出。

H_k-m(GTTA…AC)＝98778…789 (2)

公式2涉及图1的示例和k聚体集104中的第一k聚体“GTTA...AC”。在公式1中，散列操作模块108基于散列函数H_k-mer和k聚体GTTA...AC计算散列值98778...789，其中值98778...789表示介于1和2⁶⁴-1之间的值，并且“GTTA...AC”表示由k聚体集104中的k聚体限定的基因组数据读段或其一部分。散列函数H_k-mer可以是如本领域的技术人员将理解的任何合适的散列函数。散列函数H_k-mer可被配置为将k聚体集104中的k聚体映射到如公式1所示的值范围内的某个值。

散列操作模块108可基于k聚体集104执行进一步操作。在图1的示例中，散列操作模块108可生成对应于k聚体GTTA...AC的散列值98778...789。散列操作模块可基于该散列值计算另一值，如公式3所示。

H_k-mer(GTTA…AC)modulo seedModValue＝98778…789modulo 8＝0 (3)

公式3示出了在图1的示例中由散列操作模块108执行的计算。对应于k聚体GTTA...AC的散列值98778...789用于计算第二值。第二值是对散列值98778...789执行取模操作的结果。取模操作是基于散列值98778...789和seedModValue。seedModValue是预先确定的或由散列操作模块108或计算机106响应于k聚体集104而确定。在图1的示例中，seedModValue是整数8。然而，seedModValue可以是任何整数。seedModValue可基于优化操作或其他使用情况来优化或更改。seedModValue可以是根据具体实施的任何值。

散列操作模块108可基于所计算的散列值112和seedModValue生成第二k聚体集110。任何合适的规则集都可由散列操作模块108应用以生成第二k聚体集110。在图1的示例中，散列操作模块108可生成散列值98778...789，并且基于在当前示例中等于8的seedModValue对散列值98778...789执行取模操作。取模操作和结果在公式3中示出。结果为0。根据图1所示的散列操作模块108的内部规则，0的结果使散列操作模块108将对应k聚体(在这种情况下为k聚体GTTA...AC)包括在第二k聚体集110中。k聚体GTTA...AC没有划掉，这表明第二k聚体集110包括k聚体GTTA...AC。

散列操作模块108还可计算k聚体集104中所包括的其他k聚体的散列值。k聚体集104中的k聚体TATA...CG用于计算所计算的散列值112中的散列值65432...611。如上所讨论，散列操作模块108可使用seedModValue执行取模操作。在这种情况下，散列操作模块108可计算出值2。散列操作模块108可基于应用于散列值65432...611的取模操作的结果的值确定不将k聚体TATA...CG包括在第二k聚体集110中。在图1的示例中，k聚体TATA...CG被划掉，这表明k聚体TATA...CG不包括在第二k聚体集110中。

散列操作模块108可计算k聚体集104中的其他k聚体的对应散列值。如上所讨论，散列操作模块可通过对k聚体集104中的k聚体执行操作来过滤k聚体集104中的k聚体。在图1的示例中，散列操作模块108可计算散列值和应用于所计算的散列值的取模操作的结果。基于取模操作的结果，散列操作模块108可过滤k聚体集104中的k聚体并且生成第二k聚体集110。在一些具体实施中，过滤后的k聚体集诸如第二k聚体集110将包括k聚体中的散列操作(例如，取模8操作或其他合适的操作)针对其产生计算结果0的每个k聚体。也就是说，具有散列值的k聚体中的在由散列操作模块108对其进行操作时产生不同于0的结果的每个k聚体被滤除。第二k聚体集110是k聚体集104的子集。然而，本公开绝不限于为了执行过滤器操作而使用取模8操作或对散列值使用取模操作。如本领域的技术人员将理解的，可使用各种其他过滤技术。

在一些具体实施中，过滤可包括在计算机上运行的各种计算机程序。例如，如以下算法1所示，计算机程序可启动一个或多个系统变量并且基于该一个或多个系统变量执行一个或多个操作。在一些情况下，“如果”声明或其他条件译码操作可用于确定要过滤的项。

算法1在参考基因组上进行种子选择

在一些具体实施中，可使用过滤技术从基因组数据提取一个或多个项。例如，提取模块可以预先确定的间隔在亲本数据存储库内提取k聚体，该亲本数据存储库例如基因组序列、包括基因组数据的数据结构或其他形式的有序数据存储库。在一些具体实施中，提取模块可定位序列内的第一k聚体。然后，提取模块可定位序列内的第二k聚体，其中第二k聚体与第一k聚体分隔预先确定数量的核苷酸s。在这种情况下，s可以是大于0的整数。第三k聚体可使用与用于基于第一k聚体找到第二k聚体相同的间隔s来确定。操作可继续，直到满足预先确定的结束条件，例如，找到预先确定数量的k聚体或当提取模块已经到达序列末尾时。在一些具体实施中，上述示例可用于过滤其他形式的数据存储库。例如，固定间隔可用于从k聚体集104提取一个或多个元素，由此过滤k聚体集104。提取模块可定位数据结构诸如k聚体集104内的第一k聚体，并且然后定位k聚体集104内的第二k聚体，其中第二k聚体与第一k聚体分隔预先确定数量的索引i。在没有索引的数据存储库中，计数或其他值可用于标示相邻所提取元素之间的固定间距。

在一些具体实施中，有序数据集内的项可基于使用预先确定的间隔的过滤方法的一个或多个条件来选择。例如，如上所讨论，有序数据集可基于从有序数据集提取的一个或多个项来过滤。从有序数据集提取的一个或多个项的相邻项可彼此分隔预先确定的间隔。在一些具体实施中，第一值被选择成以便基于预先确定的间隔选择有序数据集中的一个或多个项。在一些情况下，第一值是以类似方式或按照等效规范在至少两个或更多个输入数据集上选择的，以产生两个或更多个输入数据集的类似过滤集。

在一些具体实施中，过滤的散列方法用于改善系统诸如图1的系统100的性能。例如，散列函数可由散列操作模块108应用于参考基因组的k聚体和基因组读段的k聚体。通过基于恒定散列函数和取模操作在参考基因组和基因组读段两者上对k聚体进行过滤，散列操作模块108可从参考基因组和基因组读段选择相同类型的k聚体。通过使用过滤的散列方法，存储器使用以及处理时间可基于以下方式减少：过滤需要索引的k聚体集，仅查询过滤操作内的k聚体的子集，以及如上所提到在参考基因组和基因组读段之间进行类似选择。

在阶段C中，出现计数器模块114可使用第二k聚体集110以将第二过滤阶段应用于k聚体集104。在一些具体实施中，出现计数器模块114可通过计算第二k聚体集110的一个或多个k聚体的基因组出现次数118来实施第二过滤阶段。每个k聚体的基因组出现次数118可包括例如特定k聚体在参考基因组(也称为参考序列)中出现的次数。在一些具体实施中，出现计数器模块114可将每个k聚体的出现次数与阈限值进行比较。在图1的示例中，阈限值定义为20。在其他具体实施中，阈限值可以是任何适用的值。

尽管本文描述了用于确定k聚体在参考序列中的出现次数的第二过滤阶段，但本公开的第二过滤阶段不限于此。相反，其他过滤器也可用于第二过滤阶段。此外，在一些具体实施中，本公开可采用零个过滤阶段、一个过滤阶段或两个或更多个过滤阶段。代替过滤阶段是本公开的限制性特征，过滤阶段在设计软件加速基因组数据映射算法期间是可定制的，以实现适合用于生成特定具体实施的散列表124的第三k聚体集116。

在图1的示例中，出现计数器模块114确定k聚体GTTA...AC在基因组数据102诸如参考序列内出现15次。不计算k聚体TATA...CG，因为k聚体TATA...CG已经在第一过滤阶段期间基于取模操作滤除。k聚体CCGA...GT在基因组数据102内出现23次，并且k聚体AAGT...AT在基因组数据102内出现11次。

基于基因组出现次数118，出现计数器模块114可将第二k聚体集110中的每个k聚体种子确定为包括在第三k聚体集116中。将基因组出现次数118的每个条目与阈限值MaxSeedOccurrence进行比较。MaxSeedOccurrence值可具有整数值诸如20。如果基因组出现次数118的项高于或等于阈限，则对应k聚体不包括在第三k聚体集116中。如果基因组出现次数118的项低于阈限，则对应k聚体包括在第三k聚体集116中。k聚体GTTA...AC和k聚体AAGT...AT均包括在第三k聚体集116中，因为对应的出现次数15和11均满足阈限MaxSeedOccurrence。第二k聚体集110中未示出的其他k聚体也可包括在第三k聚体集116中。k聚体CCGA...GT不包括在第三k聚体集116中，因为对应的出现次数23不满足阈限MaxSeedOccurrence。

如上所述，由散列操作模块108和出现计数器模块114执行的操作的至少一部分可被描述为应用于所接收的基因组数据102(诸如参考序列数据)的相应过滤阶段。在一些具体实施中，可出于多个原因使用过滤，这些原因包括例如为了减少存储器使用并减少对应于所接收数据的总体操作的计算时间。在一些具体实施中，可使用其他形式的过滤来生成所接收数据的子集。例如，诸如随机算法的算法可生成对应于所接收数据中所使用的索引的索引列表。如果索引包括在随机算法的输出中，则所接收数据的对应值可包括或不包括在数据子集中。以此方式，可生成所接收数据的子集。也可使用涉及随机数生成的其他方法，如本领域的技术人员将显而易见的。

在一些具体实施中，过滤可用于基于数据的相关特性过滤所接收的基因组数据102。例如，如图1所示，第二k聚体集110可由出现计数器模块114基于每个k聚体在基因组数据102内的出现进行过滤。在一些具体实施中，这可以是相关的过滤器，因为具有高出现计数的k聚体倾向于更可能生成将产生具有低质量分数的比对的候选比对位置。作为本说明书的动机之一，为了生成良好的候选比对，具有高出现(在图1的示例中定义为超过20的出现)的k聚体不包括于在生成散列表时将包括的所生成子集中。

在图1的阶段D中，散列表生成模块120可基于第三k聚体集116生成散列表。在图1的示例中，散列表生成模块120生成散列表124，该散列表表示为由包括签名值和位置值的数据块组成的一维数组。散列表生成模块120仅记录已经通过散列操作模块108和出现计数器模块114的过滤步骤进入散列表124中的k聚体。例如，k聚体GTTA...AC和k聚体AAGT...AT被记录到散列表124中，而k聚体TATA...CG和k聚体CCGA...GT则不。

对应于记录在散列表124中的k聚体的值可包括给定k聚体在基因组数据102内的位置。在一些具体实施中，仅k聚体在基因组数据内的第一次出现包括在给定k聚体的散列表的值数据段中。在此类具体实施中，其他位置则被丢弃。所生成的对应于k聚体GTTA...AC的值的概念性示例示出于项126中。参考126b被示出为对应于在第一次出现126a处的k聚体GTTA...AC。在图1的示例中，参考126b对应于基因组数据102。参考126b的所指出部分包括对应于k聚体GTTA...AC的序列，即，由“GTTA...AC”表示的序列中的核苷酸序列。序列“GTTA...AC”可在参考126b上的其他位置处出现，但仅序列“GTTA...AC”的第一次出现作为对应于k聚体GTTA...AC的值存储在散列表124中。

在一些具体实施中，将项插入到散列表124中可包括在计算机上运行的各种计算机程序。例如，如以下算法2所示，计算机程序可启动一个或多个系统变量并且基于该一个或多个系统变量执行一个或多个操作。在一些情况下，“如果”声明或其他条件译码操作可用于确定要过滤的项。

算法2在散列表HT中插入对(种子，位置)

使用散列函数计算对应于k聚体GTTA...AC的签名。在图1的示例中，散列函数将给定k聚体映射到0至255的范围。如项128所示，k聚体GTTA...AC用作散列函数H_sig的输入。散列表生成模块120使用散列函数H_sig将k聚体值映射到值248。然后，值248在散列表124内被用作对应于k聚体GTTA...AC的键。

通过将k聚体值映射到在0至255的范围上的数，散列表生成模块120能够减少存储在散列表124上的数据量。对于16个核苷酸长的k聚体，可需要32位来在数据结构内呈现对应数据。通过将k聚体值映射到另一值，例如，如项所示的介于0和255之间的值，减少了所需空间。例如，如果k聚体GTTA...AC包括16个核苷酸并且来自映射操作的所得签名是可用8位表达的数248，则存储在散列表124内的数据的存储器占用减少四分之一。

在一些具体实施中，其他方法可用于减少对应键，以减小散列表大小。例如，代替使用散列函数映射所接收数据的给定值，可使用值的末尾x个数位来表示可在数据结构内表达的位置。压缩散列表的数据的其他类似方法对于本领域的技术人员将是显而易见的。

在一些具体实施中，散列表124可以是指定长度的数组。例如，散列表124可包括包含N个连续单元的单个数组。散列表124还可使用线性探测技术来进行碰撞解决。在一些具体实施中，对应于散列表124的数组配置的配置可产生单个高速缓存未命中和优于其他类似方法的改善性能。通过改善散列表124的性能，可改善用于将读段映射到参考基因组的系统，诸如系统300，使得该系统可以相较于其他映射方法更高的准确度和更短的时间量生成映射结果。

可使用散列函数计算对应于k聚体GTTA...AC的索引。在图1的示例中，使用散列函数H_tab，其中H_tab与用于生成签名的H_sig散列函数不相同。在一些具体实施中，H_tab散列函数还可使用k聚体作为输入，但将输出生成为不同的值范围。由H_tab散列函数输出的值范围可对应于散列表124内可用的索引数。在一些具体实施中，散列表124可包括大约2²⁸个可被索引的单元。如项130所示，H_tab散列函数可对k聚体GTTA...AC进行操作，并且输出对应于散列表124内的索引的值268435456。分别在项126和128中示出的值和签名可在索引位置268435456处存储在散列表124内。

当查询散列表中的单元时，可使用单元的签名来识别保持特定k聚体的单元。如果找到了具有特定签名的单元，则可返回相关联的值、索引或其他参数。在一些具体实施中，多个不同的k聚体可对应于同一签名。例如，散列表124可包括对应于第一签名的第一k聚体和对应于第二签名的第二k聚体，其中表示第一签名和第二签名的值是相等的。在此类具体实施中，查询散列表以找到第一k聚体的第一签名和对应信息可导致散列表124输出与第二k聚体相关的信息。

散列表124可被设计用于低存储器使用并且用于快速查询。例如，图1的散列表124被设计来存储键值对的列表，其中键是用于识别k聚体的事物，并且值是k聚体在基因组数据102内的位置。在一些具体实施中，每k聚体存储基因组数据102内的一个位置。在一些具体实施中，存储其他位置。例如，给定k聚体在基因组数据102内的每个其他位置(例如，奇数位置等)可存储在对应于该给定k聚体的散列表中。

在一些具体实施中，散列表124可存储在计算机106的存储器内以供在阶段E处使用。例如，散列表124可在应用候选比对位置和评估时使用，如图3所示。在其他具体实施中，在阶段E处，计算机106可将散列表124发送到通信地连接到计算机106的设备。这种设备可经由一个或多个直接连接或经由一个或多个网络连接诸如通过互联网通信地连接到计算机106。在一些具体实施中，在阶段E处，散列表124可由计算机106生成并且存储在诸如拇指驱动器、硬盘驱动器的数据存储实体或其他形式的电子数据存储区内。在一些情况下，数据存储实体连接到可查询或编辑散列表124的处理器。

在一些具体实施中，计算机106可将与散列表124相关的其他数据发送到另一过程或设备。例如，代替发送散列表124，计算机106可将计算系统、算法等发送到另一过程或设备。在一些具体实施中，计算机106可将包括散列表124的数据或与散列表124相关的数据存储在存储器设备上，使得存储器设备可用于从散列表124读取数据或基于与散列表124相关的数据生成类似于散列表124的散列表。例如，计算机106可将与一个或多个模块(诸如散列操作模块108、出现计数器模块114或散列表生成模块120)相关的数据发送到另一过程或设备。与一个或多个模块相关的数据可由另一系统或系统100使用，以基于与一个或多个模块相关的数据生成一个或多个其他散列表。

在一些具体实施中，计算机106可生成散列表安装包，该散列表安装包包括用于在另一计算机上安装散列表124和基因组数据102的软件指令。在其他具体实施中，计算机106可仅提供软件指令，因为接收计算机可能已经具有基因组数据的副本。在一些具体实施中，散列表安装包可包括软件指令，这些软件指令在被执行时执行图2的过程200所述的操作。其他计算机可接收散列表安装包，执行散列表安装包，并且安装散列表124。然后，其他计算机可使用本文关于图3和图4描述的过程执行软件加速基因组读段映射。

在一些具体实施中，散列表124可使用开放寻址。例如，可通过在散列表124的数组中搜索另选位置直到找到目标单元或找到未使用单元来解决散列碰撞。单元可以是散列表124内的其中可存储数据的位置。在一些具体实施中，可使用线性探测或其他形式的探测(诸如二次探测、双重散列程序等)来确定用于存储对应于给定k聚体的数据的索引。在一些具体实施中，线性探测可用于改善的高速缓存位置，该改善的高速缓存位置可转化成比不利用线性探测的具体实施更高的性能。在图1的示例中，键和值两者都一起存储在散列表124的数组中。通过将键和值一起存储，可进一步增加高速缓存位置。

在一些具体实施中，一种形式的探测可用于生成新索引。例如，在使用线性探测的具体实施中，如果基于散列函数H_tab将第一k聚体映射到特定索引并且该索引包括具有与通过散列函数H_sig对第一k聚体计算得到的签名相同的签名的占用单元，则可计算新索引。在线性探测的情况下，索引值可增大1，直到给定索引处的签名值不等于与对第一k聚体操作的H_sig的输出相对应的签名值。当然，在给定具体实施中可使用任何其他合适的探测。

在一些具体实施中，散列表124可包括预先确定的存储器大小的单元。例如，散列表124可包括包含5个存储器字节的存储器单元。在一些具体实施中，1个字节被用于一个签名值，并且4个字节被用于分别如项128和项126所示的位置值。然而，根据具体实施，可使用其他存储器布局。

在一些具体实施中，可生成签名并将其存储在散列表124中。例如，可基于诸如k聚体GTTA...AC的给定k聚体生成签名并将其存储在散列表124中。在一些具体实施中，就数据使用而言，所生成的签名可比k聚体本身的二进制表示更小。以此方式，可进一步减少存储器使用并且可提高性能。在图1的示例中，对应于k聚体GTTA...AC的签名使用如项128所示的散列函数来生成。在这种情况下，使用散列函数H_sig。

在一些具体实施中，散列表生成模块120生成其他形式的散列表。例如，代替表示为单个数组的一维向量，散列表生成模块120可使用多个数组生成多维向量。在一些情况下，由散列表生成模块120生成的散列表的形式可基于所接收数据来确定，该所接收数据在图1的示例中是k聚体集104。例如，散列表生成模块120可将散列表的形式从具有某些特性的一维数组改变为多维向量、表格、一维数组或另一种形式的各自具有不同特性的散列索引数据库。然而，使用表示为单个数组的一维向量的具体实施提供了特定技术益处，诸如确保可不超过单次高速缓存未命中地解决散列查询。

在一些具体实施中，计算机106可被配置为执行属于散列操作模块108、出现计数器模块114和散列表生成模块120的动作。在其他具体实施中，散列操作模块108、出现计数器模块114和散列表生成模块120中的一者或多者可在通信地连接到计算机106的一个或多个设备上执行。在一些具体实施中，通信地连接到计算机106的一个或多个设备可包括其他计算机、服务器、核酸测序仪或其他设备。

在一些具体实施中，可在如图1的示例所示的处理步骤之前或之后执行一个或多个处理步骤。例如，k聚体集104在由计算机106接收之后可被预处理，以改变k聚体集104的格式，之后进行散列操作模块108的操作。

在一些具体实施中，在不偏离本说明书的范围的情况下，可移除图1的示例所示的操作中的一个或多个操作。例如，在一些情况下，散列操作模块108可将输出数据直接发送到散列表生成模块120，而无需由出现计数器模块114执行的任何操作。本领域的技术人员可考虑到各种其他修改。

又如，在一些具体实施中，系统100可在没有连续生成完整且不同的k聚体集110、116的情况下实施。相反，散列操作模块108、出现计数器模块114和散列表生成模块120的过程可以流水线方式实施。例如，散列操作模块108可计算对应于k聚体GTTA...AC的散列值98778...789，并且通过计算散列值98778...789取模seedModValue的结果来执行第一过滤阶段。如果取模操作的结果为0，则出现计数器模块114可直接接收k聚体GTTA...AC，确定对应于k聚体GTTA...AC的基因组出现次数，并且基于对应于k聚体GTTA...AC的基因组出现次数执行第二过滤阶段。一旦k聚体GTTA...AC通过出现计数器模块114的第二过滤阶段，散列表生成模块120就可以类似方式接收k聚体GTTA...AC并执行其操作，如本文所述。因此，一些具体实施，不需要生成所接收数据(诸如k聚体数据)的单独集。相反，本公开的模块可被配置为以流水线方式操作，其中后续处理模块在前一处理模块的输出生成之后对该前一处理模块的输出进行操作。这种流水线操作可导致更快地执行软件加速基因组数据映射算法。

图2是示出了用于生成用于软件加速基因组读段映射的散列表的过程200的示例的流程图。过程200可由例如图1的系统100的一个或多个电子系统执行。

系统100可通过一个或多个计算机接收基因组数据开始过程200的执行，其中该基因组数据来源于亲本基因组数据(202)。在一些具体实施中，基因组数据被解析成一个或多个k聚体。k聚体可以是包括一个或多个字段的数据结构，每个字段可表示k个核酸核苷酸或碱基中的一者或多者。

过程200包括由一个或多个计算机基于基因组数据生成第一值集(204)。在一些具体实施中，第一值集是基于散列值、散列函数或两者。例如，第一值集可包括基于基因组数据的第一k聚体的第一值。第一值可以是对散列值进行操作的取模操作符的结果，其中散列值可通过散列函数从基因组数据的第一k聚体生成。在一些具体实施中，可使用其他操作或方法来生成第一值集。例如，第一值集可包括基因组数据的给定k聚体的出现计数。

过程200包括由一个或多个计算机基于第一值集生成基因组数据的子集(206)。例如，第一值集可以是过滤数据的形式，该过滤数据用于过滤包括第一数量的k聚体的基因组数据以生成基因组数据的子集，其中该基因组数据的子集包括基于由第一值集通知的过滤的较少k聚体。

过程200包括由一个或多个计算机计算基因组数据的子集中的每个项的签名，其中该签名是基于第一散列函数计算的(208)。在一些具体实施中，散列函数可以是预先确定的。然后可使用预先确定的散列函数以基于基因组数据的子集中的给定项生成签名。在一些具体实施中，签名是基因组签名。在一些具体实施中，签名与和给定k聚体相关的数据一起存储，并且用于将与给定k聚体相关的数据识别为对应于给定k聚体的数据，如图1所示。

过程200包括由一个或多个计算机计算基因组数据的子集中的每个项的第一属性，其中该第一属性包括基因组数据的给定项在基因组数据的序列内的位置(210)。在此上下文中，项可包括k聚体种子。在一些具体实施中，第一属性仅包括基因组数据的给定项在序列内的第一次出现。例如，基因组数据的给定项可在序列内出现一次以上。为了减少将基因组数据存储在诸如散列表的数据结构中所需的存储器量，实施过程200的系统(诸如系统100)可仅存储第一次出现，而不存储给定项的任何后续出现。在一些具体实施中，计算机在给定方向上解析基因组数据表示。给定方向确定选择哪一次出现作为“第一次”出现。

过程200包括由一个或多个计算机计算基因组数据的子集中的每个项的索引，其中该索引是基于第二散列函数计算的(212)。在一些具体实施中，第二散列函数由系统100预先确定。在一些具体实施中，第二散列函数用于生成用于在诸如散列表124的散列表内定位对应于给定k聚体的数据的索引。该索引可指向与散列表124相关联的存储器内的特定位置。

过程200包括由一个或多个计算机基于基因组数据的子集中的每个项的索引，将基因组数据的子集中的每个项的签名和第一属性存储在散列数据结构内(214)。例如，如图1所示，系统100可存储如项128所示的k聚体GTTA...AC的签名和如项126所示的对应于k聚体GTTA...AC的值。在一些具体实施中，散列表124是单个数组，该单个数组在沿单个数组的单个维度的元素内存储签名和值。在一些具体实施中，散列表124内所使用的签名是作为单个字节存储的，并且作为第一属性(诸如与签名相关联的k聚体的位置)存储的值是作为4字节存储器单元存储的。在一些具体实施中，基因组数据的子集中的给定k聚体以5字节存储器单元存储在散列表124内，使得基因组数据的子集中的每个项占用散列表124的单元内的5个存储器字节。

图3是示出了使用用于软件加速基因组读段映射的散列表的系统300的示例的图。系统300包括计算机306、过滤器模块307、候选者生成模块316、排序模块322和评分与输出模块326，该过滤器模块在此示例中包括散列操作模块308和出现计数器模块310。在一些具体实施中，图1的计算机106通信地连接到计算机306。在一些具体实施中，计算机306基于由计算机106执行的过程获得散列表124或相关数据。在一些具体实施中，计算机306和计算机106是指相同设备。在一些具体实施中，计算机106、计算机306或两者可以是核酸测序仪。

在图3的示例中，基因组数据读段302是核酸序列读段。计算机306可接收基因组数据读段302并将所接收的基因组数据读段302映射到存储在散列表内的参考基因组，该散列表是使用参考图1和图2描述的系统、过程或两者中的一者或多者生成的。例如，图1中所生成的散列表124可用于存储参考基因组。基因组数据的后续读段然后可使用如图3或图4所示的过程映射到散列表124的参考基因组。

在图3的阶段A中，计算机306可获得基于基因组数据读段302生成的k聚体集304。类似于图1，k聚体集304包括在基因组数据读段302内表达至少一次的一个或多个核苷酸序列。计算机306可接收k聚体集304以供处理。在图3的示例中，k聚体集304可表示在基因组数据读段302的读段中识别的k聚体。基因组数据读段302可使用散列表(诸如图1中所生成的散列表124)映射到参考基因组。

在图3的阶段B中，散列操作模块308和出现计数器模块310可执行与参考图1的散列操作模块108和出现计数器模块114讨论的操作类似的操作。例如，散列操作模块308和出现计数器模块310对k聚体集304执行过滤，而散列操作模块108和出现计数器模块114对k聚体集104执行过滤。如本说明书中所讨论，尽管详细描述了基因组数据，但诸如计算机106和计算机306的实体可接收其他形式的所接收数据。其他形式的所接收数据可由相关模块类似地处理。处理步骤可基于所接收数据的其他形式来更改。如所讨论的，计算机306或计算机106可根据计算机306或计算机106接收的数据的形式、类型或值来更改操作。

在一些具体实施中，可使用其他形式的过滤。例如，代替使散列操作模块308和出现计数器模块310两者对k聚体集304进行操作，散列操作模块308可执行生成散列值并且基于散列值确定k聚体集304的子集的唯一过滤过程，该k聚体集的子集在此处称为第二k聚体集314。在一些情况下，代替散列操作模块308或出现计数器模块310或除了它们之外，使用另一种形式的过滤。

在一些具体实施中，过滤可包括在计算机上运行的各种计算机程序。例如，如以下算法3所示，计算机程序可启动一个或多个系统变量并且基于该一个或多个系统变量执行一个或多个操作。在一些情况下，“如果”声明或其他条件译码操作可用于确定要过滤的项。

算法3在读段上进行种子选择

类似于以上所讨论的过滤过程，包括一个或多个k聚体的k聚体集304可用于计算一个或多个散列值和表示k聚体集304中的每个k聚体在基因组数据读段302内的出现次数的一个或多个值。散列值可由散列操作模块308生成并处理，使得基于给定k聚体的散列值，散列操作模块308在系统300中的进一步处理中包括该k聚体或不包括该k聚体。出现由出现计数器模块310生成并处理，使得基于给定k聚体的出现次数，出现计数器模块310在系统300中的进一步处理中包括该k聚体或不包括该k聚体。由出现计数器模块310生成的出现值可以是给定k聚体(即，k聚体的核苷酸序列)在基因组数据读段302的较大序列内出现的次数。

在一些具体实施中，散列操作模块308可使用与参考图1讨论的取模操作类似的取模操作。散列操作模块308可计算给定散列值取模seedModValue。在一些情况下，seedModValue等于整数，诸如8。本说明书不限于任何特定数。seedModValue的值可基于优化操作或其他各种参数来更改。

在一些具体实施中，本文所讨论的一个或多个变量的特定值范围可优于其他可能的值范围。例如，MaxSeedOccurrence可增大以允许在诸如散列表124的给定散列表内索引更多k聚体。然而，增大MaxSeedOccurrence可能潜在地增加散列表124的存储器使用和大小，这可能部分地增加处理时间。非常低的值可导致较小的散列表，并且较少数据点基于散列表匹配读段，由此潜在地降低基于散列表获得的结果的准确度。各种其他权衡和效应可取决于一个或多个相关变量。例如，可基于处理状态、用户偏好、性能或其他条件更改一个或多个变量，包括指示给定k聚体或种子的长度的种子长度、指示给定读段的长度的读段长度、所使用的特定参考基因组、存储在散列表内的位置的数量或相关变量。

参考图1和图3的示例中所使用的seedModValue，在一些具体实施中，与seedModValue相关联的值可减小，以增加所得的过滤后的k聚体或其他项的集的大小。例如，在极端情况下，seedModValue可减小到值1，在这种情况下，本文所讨论的取模操作将等于0。在0是确定给定k聚体包括在过滤后的集中的值的具体实施中，取模值1意味着整个k聚体或其他项的集将用作最终的过滤后的集。在一些具体实施中，对于seedModValue，可使用较大数。例如，在极端情况下，seedModValue可增大到值100。利用高seedModValue值的所得过滤操作将在最终过滤结果中留下较少的项。在一些情况下，这可能导致更大数量的未映射读段。对于大约100个核苷酸的读段长度，高于100的seedModValue值将潜在地导致太多的读段未映射，并且因此通常不会导致有效处理。然而，对于大约1000个核苷酸的更长读段，更高的seedModValue值可更有利。

MaxSeedOccurrence和seedModValue两者可对散列表大小具有直接影响。给定散列表的存储器使用可定义为在过滤之后保持的种子或k聚体的数量乘以散列表中每个单元的大小和用于针对给定量的值生成足够单元的负载因子。考虑到1字节签名和4字节值导致每单元5个字节的情况，诸如散列表124的散列表中的每个单元可占用5个存储器字节。出于说明目的，考虑人类基因组的示例。人类基因组包括约30亿个核苷酸。在一些情况下，根据包括种子长度的一个或多个变量，从人类基因组可导出约30亿个k聚体。在没有任何过滤诸如在图1和图3的示例中讨论的散列过滤或出现过滤的情况下，与人类基因组相关联的过滤后的k聚体集将等于与人类基因组相关联的初始k聚体集，即，约30亿个。如果与5个字节的单元相对应地存储k聚体并且基于负载因子2生成散列表，则人类基因组可存储在30千兆字节的散列表中。在过滤的情况下，例如，在使用为8的seedModValue的散列过滤和使用为20的MaxSeedOccurrence的出现过滤的情况下，相同的人类基因组可存储在大约1.4千兆字节中。将seedModValue的值改变为4将使存储器使用增加大致一倍。在一些具体实施中，可基于给定应用的期望存储器使用选择值。可基于一个或多个优化过程选择最有利的值，该一个或多个优化过程包括自动改变一个或多个值的值，该一个或多个值包括seedModValue、MaxSeedOccurrence、种子长度、读段长度、测序错误率或任何其他相关参数。

在一些具体实施中，类似于图1的出现计数器模块114，出现计数器模块310可使用出现阈限。例如，出现计数器模块310可将针对k聚体集304中的每个k聚体计算的每个出现值与出现阈限进行比较。基于出现值和出现阈限之间的比较，出现计数器模块310在使用系统300的进一步处理中包括对应于给定出现值的k聚体或不包括该k聚体。

在图3的示例中，可对k聚体集304进行过滤以产生第二k聚体集314。第二k聚体集314是k聚体集304的子集。在一些具体实施中，第二k聚体集314基于其他过滤技术生成。例如，代替由散列操作模块308和出现计数器模块310进行处理，系统300可包括随机数生成器并且使用随机数生成器的输出来生成k聚体集304的子集。本领域已知的其他过滤技术也可用于减少给定数据集内的项的数量，使得后续数据集与初始数据集相比包括更少的项。在一些具体实施中，也可使用参考图1讨论的过滤技术，诸如随机算法或固定步幅索引。

在图3的阶段C中，候选者生成模块316生成候选比对位置320。在一些情况下，候选比对位置可称为参考序列位置。候选比对位置320包括与在参考基因组内出现与由基因组数据读段302表示的读段的数据相对应的数据的位置相对应的信息。在一些具体实施中，系统300可使用k聚体集304内对应于基因组数据读段302的k聚体，以基于这些k聚体在k聚体集304内的位置确定由基因组数据读段302表示的读段与参考基因组匹配的位置。参考基因组可存储在如图1所示的散列表中。散列表可由系统300用来确定k聚体集304中的一个或多个k聚体的对应位置。

候选者生成模块316可基于第二k聚体集314中的k聚体生成候选比对位置320。例如，如图3所示，k聚体CATT...GG对应于基因组数据读段302在参考基因组上的位置“位置X”。项318示出生成对应于k聚体CATT...GG的候选比对位置的过程。在k聚体CATT...GG通过一个或多个过滤步骤之后，在散列表318c中查询k聚体CATT...GG。在一些具体实施中，散列表318c相当于图1的散列表124。对应于与k聚体CATT...GG相对应的参考基因组位置的值318b可由候选者生成模块316获得。候选者生成模块316还获得k聚体CATT...GG在基因组数据读段302内的位置，如项318a所示。基于项318a中示出的k聚体CATT...GG在基因组数据读段302内的位置以及项318b中示出的k聚体CATT...GG在对应于散列表318c的参考基因组内的位置，候选者生成模块316可确定与基因组数据读段302映射在对应于k聚体CATT...GG的参考基因组上的映射相对应的位置“位置X”。

在一些具体实施中，候选者生成模块316可基于一个或多个所获得位置计算一个或多个位置。例如，对于k聚体CATT...GG，候选者生成模块316可获得项318a中示出的k聚体CATT...GG在基因组数据读段302内的位置以及项318b中示出的k聚体CATT...GG在对应于散列表318c的参考基因组内的位置，并且基于这两个位置计算位置“位置X”。例如，在匹配序列的位置作为两个或更多个读段之间的匹配序列的开始存储的具体实施中，候选者生成模块316可基于将k聚体CATT...GG在基因组数据读段302内的位置从k聚体CATT...GG在对应于参考基因组的散列表318c内的位置减去来生成位置“位置X”。候选者生成模块316可使用类似方法生成k聚体CATT...GG、AGTC...CT和GGAT...CC的位置。

在图3的阶段D中，排序模块322可对候选比对位置320进行排序。一般来讲，可使用任何合适的排序技术。在图3的示例中，排序模块322可基于所计算计数对候选比对位置320进行排序。所计算计数表示候选比对位置320中的给定候选比对位置的支持k聚体的数量。例如，候选比对位置320中的一个或多个位置可以是指示第二k聚体集314中的两个或更多个k聚体对应于基因组数据读段302在由散列表318c表示的参考基因组上的相同比对的复制。如果两个k聚体对应于相同比对，则该比对的计数为2。在图3的示例中，位置“位置X”的计数为计数X，位置“位置Y”的计数为计数Y，并且位置“位置Z”的计数为计数Z。可按递减次序对比对进行排序，使得大于计数X和计数Z的计数Y导致位置Y被存储在位置X和位置Z上方。类似地，计数X大于计数X，从而导致位置X被存储在位置Z上方。在图3的示例中，可按递减次序对比对位置进行排序，但本文设想到其他可能的排序次序。

可使用基于递减次序对比对进行排序，以便优化比对处理步骤。例如，与具有更少数量的支持k聚体的比对相比，具有更大数量的支持k聚体的比对倾向于具有更少的不匹配。可研究每个k聚体以在选择最终比对之前确定不匹配的数量。通过将这些比对处理成更可能首先通过一组标准，系统300可加速比对的处理。

在阶段E中，评分与输出模块326可获得所排序的候选比对列表324中对应于位置Y的第一位置。基于对应于散列表318c的参考基因组对位置Y进行评分。在图3的示例中，评分与输出模块326可计算基因组数据之间的不匹配的数量，该基因组数据诸如对应于k聚体AGTC...CT的与位置Y相关联的基因组数据读段302和对应于散列表318c的参考基因组数据，其中参考基因组数据用于生成散列表318c。不匹配可以是指基因组数据读段302的核苷酸与参考基因组数据的核苷酸不匹配。例如，在沿匹配序列的给定位置处，一个序列可对应于核苷酸A，而另一个序列可对应于核苷酸G。这种不匹配可由评分与输出模块326计算。

评分与输出模块326可生成对应于比对位置Y的不匹配的总数并且生成分数A，其中分数A表示至少一定数量的不匹配。在一些情况下，可使用其他参数或值来生成包括分数A的分数328。在图3的示例中，评分与输出模块326可将分数A与阈限值330进行比较。一般来讲，阈限值330可以是任何合适的值。在图3的示例中，阈限值330等于值4，其中4表示不匹配的数量。在一些具体实施中，可使用其他值。例如，优化过程可用于确定阈限值330的另一合适值。评分与输出模块326可基于将分数A与阈限值330进行比较来确定分数A不满足阈限并且因此不选择位置Y。然后，评分与输出模块326可处理一个或多个其他位置。

评分与输出模块326可生成对应于比对位置X的不匹配的总数并且生成分数B，其中分数B表示至少一定数量的不匹配。在图3的示例中，评分与输出模块326可将分数B与阈限值330进行比较。评分与输出模块326可基于分数B与阈限值330的比较确定分数B满足阈限值330。基于确定分数B满足阈限值330，评分与输出模块326可输出所选择的候选者332。所选择的候选者332可包括表示k聚体CATT...GG、位置X或分数B的数据。

在一些具体实施中，没有分数满足标准。在这种情况下，可基于给定标准从分数328中选择一个分数。例如，给定标准可包括比较分数328中的一个或多个分数以确定表示与最少量的不匹配的比对的最小分数。然后，可将对应于最低分数的位置作为所选择的候选者输出。

在阶段F中，计算机306可获得所选择的候选者332并且将表示所选择的候选者332的数据334发送到另一实体或过程。在一些情况下，计算机306可通过通信网络将数据334发送到另一实体或设备。例如，另一设备可发送对与基因组数据读段302相关联的所选择的候选者的请求。然后，计算机306可将所选择的候选者332发送到另一设备。

图4是示出了用于生成用于软件加速基因组读段映射的散列表的过程400的示例的流程图。过程400可由例如图3的系统300的一个或多个电子系统执行。

过程400包括由一个或多个计算机从基因组数据读段获得k聚体种子(402)。在一些具体实施中，k聚体种子是基于与基因组数据读段相关联的较长核苷酸序列的核苷酸序列的表示。在一些具体实施中，基因组数据读段是对计算机或硬件加速设备执行的读段分析操作的结果。

过程400包括由一个或多个计算机基于所获得的k聚体种子生成基因组签名(404)。在一些具体实施中，图3的候选者生成模块316部分地用于生成所获得的k聚体种子的签名。在一些具体实施中，所获得的k聚体种子的签名是基于散列函数生成的。例如，散列函数可对所获得的k聚体种子的表示进行操作。散列函数可生成可用作基因组签名的结果。在一些具体实施中，可在散列函数生成结果之前或之后采用一个或多个中间处理步骤。例如，散列函数可生成结果，并且可对该结果应用第二操作以生成基因组签名。

过程400包括由一个或多个计算机使用散列数据结构确定与k聚体种子的至少一部分匹配的一个或多个参考序列位置(406)。在一些具体实施中，散列数据结构包括N个数据单元，这些数据单元包括第一部分和第二部分，该第一部分存储预先确定的基因组签名，该第二部分存储与预先确定的基因组签名所来源于的k聚体种子的至少一部分匹配的一个或多个参考序列位置。在一些具体实施中，预先确定的基因组签名占用1个存储器存储字节。在一些具体实施中，与生成图1所示的散列表124的过程类似地生成散列数据结构。

过程400包括由一个或多个计算机基于一个或多个比对分数选择所确定的参考序列位置中的至少一个参考序列位置作为所获得的k聚体种子的实际比对(408)。在一些具体实施中，确定一个或多个位置，并且使用对一个或多个位置进行评分的方法，以便基于一个或多个比对分数确定所获得的k聚体种子的实际比对。例如，可计算给定比对的不匹配的数量，其中一定数量的不匹配可包括读段的一个或多个核苷酸与参考核苷酸序列的一个或多个核苷酸不匹配。这些不匹配可基于读段的一个或多个核苷酸的表示和参考核苷酸序列的一个或多个核苷酸的表示以及这两者之间基于读段相对于参考核苷酸序列的给定候选起始位置的比较来计算。

图5是可用于实施用于使用联合模型基于多变量有序数据生成医学分析的系统的计算机系统500部件的图。

计算设备500旨在表示各种形式的数字计算机，诸如膝上型计算机、台式计算机、工作站、个人数字助理、服务器、刀片式服务器、大型机和其他适当的计算机。计算设备550旨在表示各种形式的移动设备，诸如个人数字助理、移动电话、智能电话和其他类似的计算设备。另外，计算设备500或550可包括通用串行总线(USB)闪存驱动器。USB闪存驱动器可存储操作系统和其他应用程序。USB闪存驱动器可包括输入/输出部件，诸如可插入到另一个计算设备的USB端口中的无线发射器或USB连接器。此处所示的部件、它们的连接和关系以及它们的功能仅意在作为示例，并不意在限制本文档中描述和/或要求保护的本发明的具体实施。

计算设备500包括处理器502、存储器504、存储设备506、连接到存储器504和高速扩展端口510的高速接口508和连接到低速总线514和存储设备506的低速接口512。部件502、504、506、508、510和512中的每个部件使用各种总线互连，并且可安装在公共主板上或视情况以其他方式安装。处理器502可处理用于在计算设备500内执行的指令，包括存储在存储器504中或存储设备506上的指令，以在外部输入/输出设备(诸如耦接到高速接口508的显示器516)上显示GUI的图形信息。在其他具体实施中，可视情况将多个处理器和/或多个总线与多个存储器和多种类型的存储器一起使用。另外，可连接多个计算设备500，每个设备提供必要操作的一些部分，例如，作为服务器库、一组刀片式服务器或多处理器系统。

存储器504将信息存储在计算设备500内。在一个具体实施中，存储器504是一个或多个易失性存储器单元。在另一具体实施中，存储器504是一个或多个非易失性存储器单元。存储器504还可以是另一种形式的计算机可读介质，诸如磁盘或光盘。

存储设备506能够为计算设备500提供海量存储。在一个具体实施中，存储设备506可以是或包含计算机可读介质，诸如软盘设备、硬盘设备、光盘设备或磁带设备、闪存存储器或其他类似的固态存储器设备，或设备阵列，包括存储区域网络中的设备或其他配置。计算机程序产品可在信息载体中有形地体现。计算机程序产品还可包含指令，该指令在被执行时，执行一种或多种方法，诸如上文所述的那些方法。信息载体是计算机可读介质或机器可读介质，诸如存储器504、存储设备506或处理器502上的存储器。

高速控制器508管理计算设备500的带宽密集型操作，而低速控制器512管理带宽较不密集型操作。这种功能分配仅为示例。在一个具体实施中，高速控制器508例如通过图形处理器或加速器耦接到存储器504、显示器516，并且耦接到高速扩展端口510，该端口可接受各种扩展卡(未示出)。在该具体实施中，低速控制器512耦接到存储设备506和低速扩展端口514。低速扩展端口(该端口可包括各种通信端口，例如USB、蓝牙、以太网、无线以太网)可例如通过网络适配器耦接到一个或多个输入/输出设备，诸如键盘、指向设备、麦克风/扬声器对、扫描仪或联网设备诸如交换机或路由器。计算设备500可以多种不同的形式实施，如图所示。例如，该计算设备可被实施为标准服务器520，或者在一组此类服务器中被实施多次。它还可被实施为机架式服务器系统524的一部分。此外，该计算设备可在个人计算机诸如膝上型计算机522中实施。另选地，来自计算设备500的部件可与移动设备(未示出)诸如设备550中的其他部件组合。此类设备中的每个设备可包含计算设备500、550中的一个或多个设备，并且整个系统可由彼此通信的多个计算设备500、550组成。

计算设备500可以多种不同的形式实施，如图所示。例如，该计算设备可被实施为标准服务器520，或者在一组此类服务器中被实施多次。它还可被实施为机架式服务器系统524的一部分。此外，该计算设备可在个人计算机诸如膝上型计算机522中实施。另选地，来自计算设备500的部件可与移动设备(未示出)诸如设备550中的其他部件组合。此类设备中的每个设备可包含计算设备500、550中的一个或多个设备，并且整个系统可由彼此通信的多个计算设备500、550组成。

计算设备550包括处理器552、存储器564和输入/输出设备诸如显示器554、通信接口566和收发器568，以及其他部件。设备550还可设置有存储设备，诸如微驱动器或其他设备，以提供额外的存储。部件550、552、564、554、566和568中的每个部件使用各种总线互连，并且这些部件中的若干部件可安装在公共主板上或视情况以其他方式安装。

处理器552可执行计算设备550内的指令，包括存储在存储器564中的指令。处理器可被实现为包括独立的多个模拟处理器和数字处理器的芯片的芯片组。另外，处理器可使用多种架构中的任一种架构来实现。例如，处理器510可以是CISC(复杂指令集计算机)处理器、RISC(精简指令集计算机)处理器或MISC(最小指令集计算机)处理器。处理器可提供例如设备550的其他部件的协调，诸如对用户接口的控制、由设备550运行的应用程序以及由设备550进行的无线通信。

处理器552可通过耦接到显示器554的控制接口558和显示接口556与用户通信。显示器554可为例如TFT(薄膜晶体管液晶显示器)显示器或OLED(有机发光二极管)显示器或其他适当的显示技术。显示接口556可包括用于驱动显示器554以向用户呈现图形和其他信息的适当电路。控制接口558可接收来自用户的命令并转换这些命令以提交给处理器552。此外，可提供与处理器552通信的外部接口562，以便实现设备550与其他设备的近距区域通信。外部接口562可例如在一些具体实施中提供有线通信，或在其他具体实施中提供无线通信，并且还可使用多个接口。

存储器564将信息存储在计算设备550内。存储器564可被实施为一个或多个计算机可读介质、一个或多个易失性存储器单元或一个或多个非易失性存储器单元中的一者或多者。还可提供扩展存储器574并通过扩展接口572将其连接到设备550，该扩展接口可包括例如SIMM(单列直插式存储器模块)卡接口。此类扩展存储器574可为设备550提供额外的存储空间，或者还可为设备550存储应用程序或其他信息。具体地，扩展存储器574可包括用于执行或补充上述过程的指令，并且还可包括安全信息。因此，例如，扩展存储器574可被提供为用于设备550的安全模块，并且可被编程为具有允许设备550安全使用的指令。此外，安全应用程序可经由SIMM卡连同附加信息一起提供，诸如将识别信息以不可破解的方式放置在SIMM卡上。

存储器可包括例如闪存存储器和/或NVRAM存储器，如下所述。在一个具体实施中，计算机程序产品在信息载体中有形地体现。计算机程序产品包含指令，该指令在被执行时，执行一种或多种方法，诸如上文所述的那些方法。信息载体是计算机可读介质或机器可读介质，诸如存储器564、扩展存储器574或处理器552上的可通过例如收发器568或外部接口562接收的存储器。

设备550可通过通信接口566进行无线通信，该通信接口在需要时可包括数字信号处理电路。通信接口566可以提供在各种模式或协议下的通信，诸如GSM语音呼叫、SMS、EMS或MMS信息收发、CDMA、TDMA、PDC、WCDMA、CDMA2000或GPRS等。此类通信可通过例如射频收发器568发生。此外，可发生近程通信，诸如使用蓝牙、Wi-Fi或其他此类收发器(未示出)。此外，GPS(全球定位系统)接收器模块570可向设备550提供附加的导航相关和位置相关的无线数据，该无线数据可由在设备550上运行的应用程序视情况使用。

设备550还可使用音频编解码器560可听地通信，该音频编解码器可从用户接收口头信息并将其转换为可用的数字信息。音频编解码器560同样可诸如通过扬声器(例如，在设备550的手持终端中)为用户生成可听声。此类声音可包括来自语音电话呼叫的声音，可包括录制的声音，例如语音消息、音乐文件等，并且还可包括由在设备550上操作的应用程序生成的声音。

计算设备550可以多种不同的形式实施，如图所示。例如，该计算设备可被实施为移动电话580。该计算设备还可被实施为智能电话582、个人数字助理或其他类似的移动设备的一部分。

本文所述的系统和方法的各种具体实施可在数字电子电路、集成电路、特别设计的ASIC(专用集成电路)、计算机硬件、固件、软件和/或此类具体实施的组合中实现。这些各种具体实施可包括在一个或多个计算机程序中的具体实施，该一个或多个计算机程序能够在包括至少一个可编程处理器的可编程系统上执行和/或解释，该至少一个可编程处理器可以是专用或通用处理器，被耦接以从存储系统、至少一个输入设备和至少一个输出设备接收数据和指令以及将数据和指令发送到存储系统、至少一个输入设备和至少一个输出设备。

这些计算机程序(也称为程序、软件、软件应用程序或代码)包括用于可编程处理器的机器指令，并且可以高级程序化和/或面向对象的编程语言和/或以汇编语言/机器语言来实现。如本文所用，术语“机器可读介质”、“计算机可读介质”是指用于向可编程处理器提供机器指令和/或数据的任何计算机程序产品、装置和/或设备，例如磁盘、光盘、存储器、可编程逻辑设备(PLD)，包括接收机器指令作为机器可读信号的机器可读介质。术语“机器可读信号”是指用于向可编程处理器提供机器指令和/或数据的任何信号。

为了提供与用户的交互，本文所述的系统和技术可在计算机上实现，该计算机具有用于向用户显示信息的显示设备(例如CRT(阴极射线管)或LCD(液晶显示器)监视器)，以及用户可用来向该计算机提供输入的键盘和指向设备(例如鼠标或轨迹球)。也可使用其他类型的设备来提供与用户的交互；例如，提供给用户的反馈可以是任何形式的感官反馈，例如视觉反馈、听觉反馈或触觉反馈；并且可以任何形式接收来自用户的输入，包括声音、语音或触觉输入。

本文所述的系统和技术可在计算系统中实现，该计算系统包括后端部件(例如，作为数据服务器)或包括中间件部件(例如，应用程序服务器)或包括前端部件(例如，具有图形用户界面或Web浏览器的客户端计算机)，用户可通过该计算系统与本文所述的系统和技术的具体实施进行交互，或者与此类后端部件、中间件部件或前端部件的任何组合进行交互。该系统的部件可通过数字数据通信的任何形式或介质(例如，通信网络)互连。通信网络的示例包括局域网(“LAN”)、广域网(“WAN”)和互联网。

该计算系统可包括客户端和服务器。客户端和服务器通常彼此远离，并且通常通过通信网络进行交互。客户端和服务器的关系借助于在相应计算机上运行并彼此具有客户端-服务器关系的计算机程序而产生。

已经描述了多个实施方案。然而，应当理解，在不脱离本发明的实质和范围的情况下，可进行各种修改。此外，附图中所示的逻辑流程不需要所示的特定顺序或有序顺序来实现所需的结果。此外，可在所述流程中提供其他步骤，或者可消除步骤，并且可将其他部件添加到所述系统或从所述系统中移除。因此，其他实施方案也在以下权利要求书的范围内。

本说明书中描述的本发明的实施方案和所有功能操作可在数字电子电路系统中实施，或在计算机软件、固件或硬件中实施，包括本说明书中公开的结构以及这些结构的结构等同物或它们中一者或多者的组合。本发明的实施方案可实施为一个或多个计算机程序产品，例如，在计算机可读介质上编码以供数据处理装置执行或控制数据处理装置的操作的计算机程序指令的一个或多个模块。计算机可读介质可以是机器可读存储设备、机器可读存储基板、存储器设备、实现机器可读传播信号的物质的组成或它们中的一者或多者的组合。术语“数据处理装置”涵盖用于处理数据的所有装置、设备和机器，包括例如可编程处理器、计算机或多个处理器或计算机。除了硬件之外，装置还可包括创建用于所讨论的计算机程序的执行环境的代码，例如构成处理器固件、协议栈、数据库管理系统、操作系统或它们中一者或多者的组合的代码。传播的信号是人工生成的信号，例如，机器生成的电气、光学或电磁信号，生成该信号以编码用于传输到合适的接收器装置的信息。

计算机程序(也称为程序、软件、软件应用程序、脚本或代码)可以任何形式的编程语言(包括编译或解释语言)编写，并且该计算机程序可以任何形式部署，包括作为独立程序或作为模块、部件、子例程或适用于计算环境中的其他单元。计算机程序不一定对应于文件系统中的文件。程序可存储在保持其他程序或数据的文件的一部分(例如，存储在标记语言文档中的一个或多个脚本)中，存储在专用于所讨论的程序的单个文件中或存储在多个协调文件(例如，存储一个或多个模块、子程序或代码部分的文件)中。计算机程序可被部署成在一个计算机上或在位于一个站点处或分布在多个站点上并通过通信网络互连的多个计算机上执行。

本说明书中描述的过程和逻辑流程可由执行一个或多个计算机程序的一个或多个可编程处理器执行，以通过对输入数据进行操作并生成输出来执行功能。过程和逻辑流程也可由专用逻辑电路执行，并且装置也可被实施为专用逻辑电路，例如FPGA(现场可编程门阵列)或ASIC(专用集成电路)。

适用于执行计算机程序的处理器包括例如通用和专用微处理器两者，以及任何种类的数字计算机的任何一个或多个处理器。通常，处理器将从只读存储器或随机存取存储器或两者接收指令和数据。计算机的基本元素是用于执行指令的处理器和用于存储指令和数据的一个或多个存储器设备。通常，计算机还将包括或可操作地耦接以从一个或多个用于存储数据的海量存储设备(例如，磁盘、磁光盘或光盘)接收数据或将数据转移到该一个或多个海量存储设备或两者。然而，计算机不需要具有此类设备。此外，计算机可嵌入另一个设备中，例如，平板计算机、移动电话、个人数字助理(PDA)、移动音频播放器、全球定位系统(GPS)接收器等等。适用于存储计算机程序指令和数据的计算机可读介质包括所有形式的非易失性存储器、介质和存储器设备，包括例如半导体存储器设备，例如，EPROM、EEPROM和闪存存储器设备；磁盘，例如内部硬盘或可移动盘；磁光盘；以及CD ROM和DVD-ROM盘。处理器和存储器可由专用逻辑电路补充或并入专用逻辑电路中。

为了提供与用户的交互，本发明的实施方案可在计算机上实施，该计算机具有用于向用户显示信息的显示设备(例如CRT(阴极射线管)或LCD(液晶显示器)监视器)，以及用户可用来向该计算机提供输入的键盘和指向设备(例如鼠标或轨迹球)。也可使用其他类型的设备来提供与用户的交互；例如，提供给用户的反馈可以是任何形式的感官反馈，例如视觉反馈、听觉反馈或触觉反馈；并且可以任何形式接收来自用户的输入，包括声音、语音或触觉输入。

本发明的实施方案可在计算系统中实施，该计算系统包括后端部件(例如，作为数据服务器)或包括中间件部件(例如，应用程序服务器)或包括前端部件(例如，具有图形用户界面或Web浏览器的客户端计算机)，用户可与本发明的具体实施或一个或多个此类后端部件、中间件部件或前端部件的任何组合进行交互。该系统的部件可通过数字数据通信的任何形式或介质(例如，通信网络)互连。通信网络的示例包括局域网(“LAN”)和广域网(“WAN”)，例如互联网。

虽然本说明书含有许多细节，但这些不应被解释为对本发明的范围或可要求保护的范围的限制，而是作为对本发明的特定实施方案特有的特征的描述。在本说明书中在单独实施方案的上下文中描述的某些特征也可以组合形式在单个实施方案中实施。相反，在单个实施方案的上下文中描述的各种特征也可以单独地或以任何合适的子组合在多个实施方案中实施。此外，尽管特征可在上文中描述为以某些组合起作用，并且甚至最初也如此要求保护，但在一些情况下，可从组合中删除来自要求保护的组合的一个或多个特征，并且所要求保护的组合可针对子组合或子组合的变型。

类似地，虽然以特定顺序在附图中描绘操作，但是这不应被理解为要求以所示的特定顺序或按顺序执行此类操作，或者要求执行所有说明的操作以实现期望的结果。在某些情况下，多任务和并行处理可能是有利的。此外，上文所描述的实施方案中各种系统部件的分离不应被理解为在所有实施方案中都需要此类分离，并且应当理解，所描述的程序部件和系统通常可集成在单个软件产品中或打包到多个软件产品中。

在提及HTML文件的每种情况下，其他文件类型或格式可被替代。例如，HTML文件可由XML、JSON、普通文本或其他类型的文件替换。此外，在提及表格或散列表的情况下，可使用其他数据结构(诸如电子表格、关系数据库或结构化文件)。

其他实施方案

已经描述了本发明的特定实施方案。其他实施方案也在以下权利要求书的范围内。例如，权利要求中叙述的步骤可以不同的顺序执行并且仍然会实现期望的结果。

Claims

1.一种用于软件加速基因组数据读段映射的方法，所述方法包括：

由一个或多个计算机从基因组数据读段获得k聚体种子；

由所述一个或多个计算机基于所获得的k聚体种子生成基因组签名；

由一个或多个计算机使用散列数据结构确定与所述k聚体种子的至少一部分匹配的参考序列位置，其中所述散列数据结构包括N个数据单元，所述数据单元包括第一部分和第二部分，所述第一部分存储预先确定的基因组签名，所述第二部分存储与同所述预先确定的基因组签名所来源于的k聚体种子的至少一部分匹配的参考序列位置的第一次出现相对应的值；以及

由一个或多个计算机基于一个或多个比对分数选择所确定的参考序列位置作为所获得的k聚体种子的实际比对。

2.根据权利要求1所述的方法，其中所述预先确定的基因组签名占用一个存储器存储字节。

3.根据任一项前述权利要求所述的方法，其中所述值占用四个存储器存储字节。

4.根据任一项前述权利要求所述的方法，其中所述散列数据结构是具有N个数据单元的单个数组。

5.根据前述权利要求中任一项所述的方法，所述方法还包括：

由一个或多个计算机基于与所述基因组数据读段的一个或多个k聚体种子相对应的第一值集过滤所述基因组数据读段。

6.根据权利要求5所述的方法，其中所述第一值集包括应用于所述基因组数据读段的所述一个或多个k聚体种子的预先确定的操作的结果，并且其中所述第一值集用于从所述基因组数据读段获得所述k聚体种子。

7.根据权利要求6所述的方法，其中所述预先确定的操作包括基于所述基因组数据读段的所述一个或多个k聚体种子和散列函数生成散列值。

8.根据前述权利要求中任一项所述的方法，其中确定所述参考序列位置包括：

由一个或多个计算机计算所述基因组数据读段的所述k聚体种子的第一位置，其中所述第一位置对应于所述k聚体种子在所述基因组数据读段内的位置；以及

由一个或多个计算机计算所述k聚体种子的第二位置，其中所述第二位置对应于所述k聚体种子在所述参考基因组数据内的位置，并且其中所述第二位置是基于所述散列数据结构计算的。

9.根据前述权利要求中任一项所述的方法，所述方法还包括：

由一个或多个计算机基于所述散列数据结构和所述基因组数据读段对所述一个或多个参考序列位置进行排序。

10.根据前述权利要求中任一项所述的方法，所述方法还包括：

由一个或多个计算机基于对所述一个或多个参考序列位置进行排序生成所述一个或多个比对分数。

11.根据前述权利要求中任一项所述的方法，其中选择所确定的参考序列位置中的至少一个参考序列位置作为所获得的k聚体种子的所述实际比对包括：将所述一个或多个比对分数与阈限值进行比较。

12.根据前述权利要求中任一项所述的方法，其中所述一个或多个比对分数包括表示来自所述基因组数据读段的所获得的k聚体种子和所述参考序列位置之间的不匹配的数量的数值。

13.根据前述权利要求中任一项所述的方法，其中丢弃在与所述预先确定的基因组签名所来源于的所述k聚体种子的至少一部分匹配的参考序列位置的第一次出现之后的每次后续出现。

14.一种用于软件加速基因组数据读段映射的系统，所述方法包括：

一个或多个计算机；以及

一个或多个存储器设备，所述一个或多个存储器设备存储指令，所述指令在由所述一个或多个计算机执行时使所述一个或多个计算机执行操作，所述操作包括：

由所述一个或多个计算机从基因组数据读段获得k聚体种子；

由所述一个或多个计算机使用散列数据结构确定与所述k聚体种子的至少一部分匹配的参考序列位置，其中所述散列数据结构包括N个数据单元，所述数据单元包括第一部分和第二部分，所述第一部分存储预先确定的基因组签名，所述第二部分存储与同所述预先确定的基因组签名所来源于的k聚体种子的至少一部分匹配的参考序列位置的第一次出现相对应的值；以及

由所述一个或多个计算机基于一个或多个比对分数选择所确定的参考序列位置作为所获得的k聚体种子的实际比对。

15.根据权利要求14所述的系统，其中所述预先确定的基因组签名占用一个存储器存储字节。

16.根据前述权利要求14或15中任一项所述的系统，其中所述值占用四个存储器存储字节。

17.根据前述权利要求14至16中任一项所述的系统，其中所述散列数据结构是具有N个数据单元的单个数组。

18.根据前述权利要求14至17中任一项所述的系统，所述操作还包括：

由所述一个或多个计算机基于与所述基因组数据读段的一个或多个k聚体种子相对应的第一值集过滤所述基因组数据读段。

19.根据权利要求18所述的系统，其中所述第一值集包括应用于所述基因组数据读段的所述一个或多个k聚体种子的预先确定的操作的结果，并且其中所述第一值集用于从所述基因组数据读段获得所述k聚体种子。

20.根据权利要求19所述的系统，其中所述预先确定的操作包括基于所述基因组数据读段的所述一个或多个k聚体种子和散列函数生成散列值。

21.根据前述权利要求14至20中任一项所述的系统，其中确定所述参考序列位置包括：

由所述一个或多个计算机计算所述基因组数据读段的所述k聚体种子的第一位置，其中所述第一位置对应于所述k聚体种子在所述基因组数据读段内的位置；以及

由所述一个或多个计算机计算所述k聚体种子的第二位置，其中所述第二位置对应于所述k聚体种子在所述参考基因组数据内的位置，并且其中所述第二位置是基于所述散列数据结构计算的。

22.根据前述权利要求14至21中任一项所述的系统，其中所述操作还包括：

由所述一个或多个计算机基于所述散列数据结构和所述基因组数据读段对所述一个或多个参考序列位置进行排序。

23.根据前述权利要求14至22中任一项所述的系统，所述操作还包括：

24.根据前述权利要求14至23中任一项所述的系统，其中选择所确定的参考序列位置中的至少一个参考序列位置作为所获得的k聚体种子的所述实际比对包括：将所述一个或多个比对分数与阈限值进行比较。

25.根据前述权利要求14至24中任一项所述的系统，其中所述一个或多个比对分数包括表示来自所述基因组数据读段的所获得的k聚体种子和所述参考序列位置之间的不匹配的数量的数值。

26.根据前述权利要求14至25中任一项所述的系统，其中丢弃在与所述预先确定的基因组签名所来源于的所述k聚体种子的至少一部分匹配的参考序列位置的第一次出现之后的每次后续出现。

27.一种存储指令的计算机可读介质，所述指令在由一个或多个计算机执行时使所述一个或多个计算机执行用于软件加速基因组数据读段映射的操作，所述操作包括：

从基因组数据读段获得k聚体种子；

基于所获得的k聚体种子生成基因组签名；

使用散列数据结构确定与所述k聚体种子的至少一部分匹配的参考序列位置，其中所述散列数据结构包括N个数据单元，所述数据单元包括第一部分和第二部分，所述第一部分存储预先确定的基因组签名，所述第二部分存储与同所述预先确定的基因组签名所来源于的k聚体种子的至少一部分匹配的参考序列位置的第一次出现相对应的值；以及

基于一个或多个比对分数选择所确定的参考序列位置作为所获得的k聚体种子的实际比对。

28.根据权利要求27所述的计算机可读介质，其中所述预先确定的基因组签名占用一个存储器存储字节。

29.根据前述权利要求27或28中任一项所述的计算机可读介质，其中所述值占用四个存储器存储字节。

30.根据前述权利要求27至29中任一项所述的计算机可读介质，其中所述散列数据结构是具有N个数据单元的单个数组。

31.根据前述权利要求27至30中任一项所述的计算机可读介质，所述操作还包括：

基于与所述基因组数据读段的一个或多个k聚体种子相对应的第一值集过滤所述基因组数据读段。

32.根据权利要求31所述的计算机可读介质，其中所述第一值集包括应用于所述基因组数据读段的所述一个或多个k聚体种子的预先确定的操作的结果，并且其中所述第一值集用于从所述基因组数据读段获得所述k聚体种子。

33.根据前述权利要求27至32中任一项所述的计算机可读介质，其中确定所述参考序列位置包括：

计算所述基因组数据读段的所述k聚体种子的第一位置，其中所述第一位置对应于所述k聚体种子在所述基因组数据读段内的位置；以及

计算所述k聚体种子的第二位置，其中所述第二位置对应于所述k聚体种子在所述参考基因组数据内的位置，并且其中所述第二位置是基于所述散列数据结构计算的。

34.根据前述权利要求27至33中任一项所述的计算机可读介质，其中所述操作还包括：

基于所述散列数据结构和所述基因组数据读段对所述一个或多个参考序列位置进行排序。

35.根据前述权利要求27至34中任一项所述的计算机可读介质，所述操作还包括：

基于对所述一个或多个参考序列位置进行排序生成所述一个或多个比对分数。

36.根据前述权利要求27至35中任一项所述的计算机可读介质，其中选择所确定的参考序列位置中的至少一个参考序列位置作为所获得的k聚体种子的所述实际比对包括：将所述一个或多个比对分数与阈限值进行比较。

37.根据前述权利要求27至36中任一项所述的计算机可读介质，其中所述一个或多个比对分数包括表示来自所述基因组数据读段的所获得的k聚体种子和所述参考序列位置之间的不匹配的数量的数值。

38.根据前述权利要求27至37中任一项所述的计算机可读介质，其中丢弃在与所述预先确定的基因组签名所来源于的所述k聚体种子的至少一部分匹配的参考序列位置的第一次出现之后的每次后续出现。

39.一种用于生成用于软件加速基因组数据读段映射的散列表的方法，所述方法包括：

由一个或多个计算机接收基因组数据，其中所述基因组数据来源于亲本基因组数据；

由所述一个或多个计算机基于所述基因组数据生成第一值集；

由一个或多个计算机基于所述第一值集生成所述基因组数据的子集；

由一个或多个计算机计算所述基因组数据的所述子集中的每个k聚体的签名，其中所述签名是基于第一散列函数计算的；

由一个或多个计算机计算所述基因组数据的所述子集中的每个k聚体的索引，其中所述索引是基于第二散列函数计算的；以及

由一个或多个计算机基于所述基因组数据的所述子集中的每个k聚体的所述索引将所述基因组数据的所述子集中的每个k聚体的所述签名和所述第一属性存储在散列数据结构内。

40.根据权利要求39所述的方法，其中所述基因组数据的所述子集中的每个k聚体是包括表示一串一个或多个核苷酸的k个字母的k聚体。

41.根据权利要求39或40中任一项所述的方法，其中所述第一值集包括所述基因组数据的给定k聚体在所述亲本基因组数据内出现的次数的表示。

42.根据前述权利要求39至41中任一项所述的方法，其中所述第一值集包括基于所述基因组数据的对应k聚体计算的散列值的表示。

43.根据前述权利要求39至42中任一项所述的方法，其中用于存储所述子集中的给定k聚体的签名的存储器分配大小小于用于存储所述给定k聚体的存储器分配大小。

44.根据前述权利要求39至43中任一项所述的方法，所述方法还包括：

由所述一个或多个计算机将对应于所述散列数据结构的数据作为数据包发送到第一设备。

45.根据权利要求44所述的方法，其中所述第一设备是存储器存储设备。

46.根据权利要求44或权利要求45所述的方法，其中第二设备从所述第一设备读取对应于所述散列数据结构的所述数据，并且其中所述第二设备执行一连串操作以基于对应于所述散列数据结构的所述数据生成第二散列数据结构。

47.一种用于生成用于软件加速基因组数据读段映射的散列表的系统，所述系统包括：

一个或多个计算机；以及

一个或多个存储器，所述一个或多个存储器存储指令，所述指令在由所述一个或多个计算机执行时使所述一个或多个计算机执行操作，所述操作包括：

由所述一个或多个计算机接收基因组数据，其中所述基因组数据来源于亲本基因组数据；

由所述一个或多个计算机基于所述第一值集生成所述基因组数据的子集；

由所述一个或多个计算机计算所述基因组数据的所述子集中的每个k聚体的签名，其中所述签名是基于第一散列函数计算的；

由所述一个或多个计算机计算所述基因组数据的所述子集中的每个k聚体的第一属性，其中所述第一属性包括所述基因组数据的给定k聚体在所述基因组数据的序列内的位置；

由所述一个或多个计算机计算所述基因组数据的所述子集中的每个k聚体的索引，其中所述索引是基于第二散列函数计算的；以及

由所述一个或多个计算机基于所述基因组数据的所述子集中的每个k聚体的所述索引将所述基因组数据的所述子集中的每个k聚体的所述签名和所述第一属性存储在散列数据结构内。

48.根据权利要求47所述的系统，其中所述基因组数据的所述子集中的每个k聚体是包括表示一串一个或多个核苷酸的k个字母的k聚体。

49.根据前述权利要求47或48中任一项所述的系统，其中所述第一值集包括所述基因组数据的给定k聚体在所述亲本基因组数据内出现的次数的表示。

50.根据前述权利要求47至49中任一项所述的系统，其中所述第一值集包括基于所述基因组数据的对应k聚体计算的散列值的表示。

51.根据前述权利要求47至50中任一项所述的系统，其中用于存储所述子集中的给定k聚体的签名的存储器分配大小小于用于存储所述给定k聚体的存储器分配大小。

52.根据前述权利要求47至51中任一项所述的系统，其中所述操作还包括：

53.根据权利要求52所述的系统，其中所述第一设备是存储器存储设备。

54.根据权利要求52或权利要求53所述的系统，其中第二设备从所述第一设备读取对应于所述散列数据结构的所述数据，并且其中所述第二设备执行一连串操作以基于对应于所述散列数据结构的所述数据生成第二散列数据结构。

55.一种存储指令的计算机可读介质，所述指令在由一个或多个计算机执行时使所述一个或多个计算机执行用于生成用于软件加速基因组数据读段映射的散列表的操作，所述操作包括：

接收基因组数据，其中所述基因组数据来源于亲本基因组数据；

基于所述基因组数据生成第一值集；

基于所述第一值集生成所述基因组数据的子集；

计算所述基因组数据的所述子集中的每个k聚体的签名，其中所述签名是基于第一散列函数计算的；

计算所述基因组数据的所述子集中的每个k聚体的第一属性，其中所述第一属性包括所述基因组数据的给定k聚体在所述基因组数据的序列内的位置；

计算所述基因组数据的所述子集中的每个k聚体的索引，其中所述索引是基于第二散列函数计算的；以及

基于所述基因组数据的所述子集中的每个k聚体的所述索引将所述基因组数据的所述子集中的每个k聚体的所述签名和所述第一属性存储在散列数据结构内。

56.根据权利要求55所述的计算机可读介质，其中所述基因组数据的所述子集中的每个k聚体是包括表示一串一个或多个核苷酸的k个字母的k聚体。

57.根据权利要求55或权利要求56所述的计算机可读介质，其中所述第一值集包括所述基因组数据的给定k聚体在所述亲本基因组数据内出现的次数的表示。

58.根据前述权利要求55至57中任一项所述的计算机可读介质，其中所述第一值集包括基于所述基因组数据的对应k聚体计算的散列值的表示。

59.根据前述权利要求55至58中任一项所述的计算机可读介质，其中用于存储所述子集中的给定k聚体的签名的存储器分配大小小于用于存储所述给定k聚体的存储器分配大小。

60.根据前述权利要求55至59中任一项所述的计算机可读介质，所述操作还包括：

将对应于所述散列数据结构的数据作为数据包发送到第一设备。

61.根据权利要求60所述的计算机可读介质，其中所述第一设备是存储器存储设备。

62.根据权利要求60或权利要求61所述的计算机可读介质，其中第二设备从所述第一设备读取对应于所述散列数据结构的所述数据，并且其中所述第二设备执行一连串操作以基于对应于所述散列数据结构的所述数据生成第二散列数据结构。