该主题是作为讨论线程创建的。它提出了几个问题，因此您可以同时回答所有问题和其中一个问题。我给出了一些问题的答案，而不是它是正确的事实。如果有很多兴趣，您可以尝试组织聊天进行讨论。
生物信息学中最常见的任务：在字符串中查找子字符串。在大多数情况下，这是以一种标准方式实现的，不需要大量资源，也不值得详细考虑。但是，在我看来，有一类问题可以通过使用加载的树来加速/简化。
在本主题中，我们将仅考虑精确搜索。
术语解释：
参考：一个长的 DNA 序列，通常包含部分染色体或整个染色体/基因组的转录本。表示（通常）由 A、G、T、C（表示不同的核苷酸）和 N 组成的字符串 - 一个字符，表示任何核苷酸，或不存在确切信息。示例：AAGGCCTCGTCNTTNNGCCC...
模式（或读取）：一个短的 DNA 序列，一个包含与上述相同字符的字符串，长度从 1（当然没有意义，但它发生）到几千的合理值。我们主要处理 30 到 300 个字母的长度，但还有其他任务。
回文-互补字符串，即 根据特殊规则倒序（从末尾读取字符串，按规则替换字母：A -> T，C -> G，G -> C，T -> A，N -> N）
对于航班的分析，我们将考虑人类第8条染色体作为参考（A：43333530，C：29030173，G：29103787，T：43300646，N：370500条，总共145138636个字母）。为简单起见，读取长度为 100 个字母。
马上我会告诉我我将在 Delphi 上编写代码。总的来说，我不在乎 - Delphi、c++、c# 或 java，但 Delphi 对我来说更熟悉。
问题 1. 创建树形结构。类或链表。
2个树实现选项：
班级
type
AGTCIndex = (A, C, G, T);
TTrie = class
fAmI: integer; // кто я - на всякий случай
fParent: TTrie; // ссылка на родительский узел
fChildren:array[AGTCIndex] of TTrie; // ссылка на узлы потомков
fCount: array of longint; // для адресации 145 миллионов хватит. Вот если бы работали с геномом секвойи, стоило бы использовать int64 :)
<...>
end;
或链表
type
AGTCIndex = (A, C, G, T);
pTrie = ^TTrie;
TTrie = record
fAmI: integer; // кто я - на всякий случай
fParent: pTrie; // ссылка на родительский узел
fChildren:array[AGTCIndex] of pTrie; // ссылка на узлы потомков
fCount: array of longint;
end;
在我看来，链表更适合我们的任务：内存消耗更少，工作速度更快（我们不要在不必要的调用上浪费时间）。当然，为方便起见，我们将列表包装在一个类中。
问题二、内存消耗
在标准方法中，将花费 145 戈比的内存——这就是一条线需要多少。您可以使用半字节表示（描述及其工作原理）来欺骗和使用 2 倍。
在使用树的情况下，成本将至少为 100 * 145138636 * 16 或至少 230 GB。一切，羊皮得不偿失。可以使用的最大值为 32 GB。我们得出结论，只要参考的长度不超过 1600 万，这种方法是适用的。
原则上，这里也实现了半字节的方法。它甚至可以带来超过 2 倍的收益。但恐怕带来的不便多于好处。如果有其他意见 - 请提出意见。
问题3：精细的搜索性能
在标准方法中，在参考中找到所有包含的模式大约需要 |length(reference)*ln(length(pattern)|。如果并行化，那么内核每增加一倍大约要快 1.6 倍。
在使用树的情况下，根据我的计算，只有在前额上至少需要 O（100 * 长度）才能进行构造。使用阅读框可以减少到 O(30*length)。并行方法还将内核每增加一倍，该过程就会加快 1.6 倍。
总的来说，我们有：创建一棵树比使用标准方法搜索一个模式要多花大约 500 到 1000 倍的时间。但是，由于在已经形成的树中搜索要快得多，而且它允许您并行获取额外的数据，所以我们有： 当引用被重复使用时，创建树的好处是实现的，并且用于不同的模式。评价：至少500次。适用范围：精确映射、仪器数据的流式处理等。
没错，互补搜索存在一个小问题。事实上，我们将不得不从孩子到父母，这会有点慢。
如果主题很有趣，您可以继续进行模糊搜索，这通常更相关和更有趣。
更新 1
创建了一个聊天室
更新 2
**相对于按位表示。大声推理（几乎与树木无关）**
为什么不节省内存和时间，并使用半字节甚至四分之一字节表示？
- 我不确定。我还没有遇到过使用类似方法的单一 GNU 软件（关于付费软件 - 见下文）。所有人都否认兼容性和不愿意为按位工作编写复杂的例程。而最近他们也回答——“内存降价了”。
我对为什么每个人都不使用按位方法的看法：
兼容性并不是特别重要。毕竟，无损转换：您可以随时转换回来。但！通常，相同的程序不仅用于在 DNA 内进行搜索，还用于在蛋白质序列、基因依赖性等内进行搜索。在那里 - 拉丁字母是不够的。
AGTC 是一个非常特殊的情况。还有甲基化核苷酸、双脱氧核苷酸、“可疑”核苷酸等等。那些。“字母”远不止 4 个字母。因此，例程是“为一切”创建的。
在上面的第一个链接上，我举了一个使用半字节表示的例子，我在 2004 年“开发”了一个完整的基因组 triter（Windows 下的第一个 - 我有点自豪:)）是创建于 2006 年。然后内存很少，处理器非常愚蠢。主要思想：A=0001b，C=0010b，G=0100b，T=1000b。然后掩码非常成功地叠加在一次搜索多个选项上：N = 1111b、R（A 或 G）= 0101b、Y（C 或 T）= 1010b 等。在 SSE2 中实现了一个大字（64 或 128 位）的半字节移位，它允许您一次处理多达 32 个字母。
所以，关于这个实现，我怀疑这种方法至少用在一个商业包中:) 但是，我并不感到抱歉，特别是因为这种方法是表面上的。
更新 3
发布了问题的第二部分：生物信息学中的加载树。第 2 部分。模糊搜索
树已经很好地证明了自己，因为在只有可能键的子集的情况下，它们具有相当经济的内存消耗。假设我们需要在 3 个级别上制作一棵树。如果我们只有 AAA、ACA、GCC 选项，我们将在第一级只有两个节点“A”和“G”，在第二级有 3 个节点，“A”、“C”（对于 A）、“C” '（对于 G）和第三级 3 节点。3个核苷酸有64个可能的关键选择，总共8个节点是一个很好的结果。
现在让我们对第 8 条染色体的文本进行统计分析……我们主要感兴趣的是所有可能的键值与真实键值的比率。参考文献中多达 11 个字母序列，几乎存在所有可能的核苷酸排列变体。在 11 个字母中，在 400 万个可能的值中，只有 24 万个缺失（约 6%）。那些。我们需要为 11 个核苷酸的索引链创建大约 400 万个节点。
同时，通过制作类型化数组 (
of TTrie)，您可能假设链接将存储在那里。引用是指向进程内存中地址的指针。如果您创建一个索引并立即使用它，那么一切都会好起来的。但是索引成本很高，能够将其存储在磁盘上会很好。但是你不能把地址放在磁盘上的物理内存中，你需要以某种方式序列化对象，当从磁盘读取时，用物理地址重新创建它们......此外，如果为每个对象单独分配内存，那么内存经理开销出现。结果，一个节点不会像您建议的那样花费您 16 个字节，而最多花费 30 个字节...因此，对于第一个问题“上述哪种存储方法更好”的答案不是以上任何一种。你自己回答了第二个问题——内存成本太疯狂了。在第三个问题中，问题本身是缺失的，这是对索引将花费大量时间的事实的陈述（顺便说一下，通过“O”进行的评估过于近似。考虑到维护此类的间接费用）语言结构）
结合上述内容，我得出的结论是，存储这种树的初始级别的唯一紧凑方法是一个带有指向 400 万个可能键的指针的公共数组。其中只有 6% 的元素是空的。表中的索引将是由 11 个字母组成的键，以数字系统表示，其基数与字母表的大小相同（在我们的例子中，每个字母 2 位）。在文本中单个 N 的情况下，我们将它们视为所有 4 个可能的键。我们将存储多于一个 N 的区域作为区域列表（在考虑的第 8 条染色体示例中，只有 12 个这样的区域）。数组中的指针可以指向“继续”那些 11 个字符序列的树节点。或者，例如，直接到遇到此类序列的地址列表。仅对于某些键，列表非常大（11 A 和 11 T 分配有 106k 个条目）。总共有大约 740 个密钥（400 万个），包含 3000 多个地址列表。
我使用上述方法实现了索引和搜索。在指针后面，我直接存储地址列表，在搜索时，我使用它们的快速比较（指针的并行、同步移位）。他提供了 N 区域的工作，但直到最后都没有开始实施。主索引所需的内存为 32 MB。为了存储地址列表，每个地址使用 4 个字节，即 参考长度 * 4。对于 141MB 的输入文件，索引文件的总大小为 581MB。索引时间（对于 2 次参考通过）约为 30 秒（包括刷新到磁盘）。顺便说一句，这样的索引可以用来快速构建树。搜索算法没有优化，一个核心每秒只能处理大约 10-15000 个请求。免费搜索也没有实现，我看到这样一个选项，如何为互补键创建一个 16 Mb 的转换表，并通过相同的索引进行搜索，并将模式中的偏移量重新计算为相反的顺序。资源：索引、搜索（由 gcc 在 linux 下构建）
鉴于在这种特殊情况下，关键点（在我看来）是数据的大小，我建议优化这个特殊因素；（为了分析航班，我们将考虑人类第8条染色体作为参考（A：43333530，C：29030173，G：29103787，T：43300646，N：370500条，总共145138636个字母））让我们创建五个数组A , C, G, T, N 维度为 145138636 位 ... 对应数组中的第 1 位表示该位置存在核苷酸；
我会建议以下方式。由于只有4个核苷酸：
A, C, G, T和+第五个不定核苷酸N，那么基于逻辑上的5-teric数字系统本身就0=A, 1=C, 2=G, 3=T, 4=N可以分别将包含1.45亿个序列的第8条染色体编码为5-teric number，占据145/ 8 * 5 内存百万 = 90 兆字节。在这种情况下，对子字符串的搜索会退化为对 5 位掩码的搜索
在Java中，这相对容易实现
BigInteger我会给出一个更有趣的方向：模糊搜索。也许你还没有看到这个https://habrahabr.ru/post/115147/方法（“MinHash - 识别相似集合”）。如果我们稍微修改一下，考虑人类基因组有很多很多与单词重叠的窗口，那么在索引之后我们可以相对快速地搜索到我们需要的窗口（这不一定是完全匹配的）。这种方法也适用于SQL，虽然我的速度不是很快。（即最好提前计算计算复杂度。）