DNA字母表后缀数组构造算法和数据结构研究

沙特国王大学学报一种构造DNA字母表Zeinab Rabea，Sara El-MetwallyZhao，Samir Elmougy，Magdi ZakariaMansoura大学计算机与信息学院计算机科学系，Mansoura35516，埃及阿提奇莱因福奥文章历史记录：收到2022年2022年4月8日修订2022年4月26日接受2022年5月6日在线发布保留字：后缀数组DNA字母表最长公共前缀Burrows-Wheeler变换A B S T R A C T测序技术的不断改进已经被用于测序数据分析和处理的有效算法和数据结构的发展所证实。后缀数组是构造长基因组Burrows-Wheeler变换的数据结构之一。构建后缀数组本身是一个消耗资源的过程，因为计算主要是按照词法顺序对后缀进行大多数后缀数组构造算法考虑的是一般和整数字母表，而没有利用固定大小的特殊情况，如DNA字母表。在本文中，我们利用四个大小的DNA字母表的性质，并利用其预定义的字典序，以正确和有效地构建基因组数据的后缀阵列。使用三个不同长度的真实数据集，从小的大肠杆菌基因组到长长度的智人GRCh38.p13染色体的DNA字母的后缀阵列构建算法进行评估。对于长长度基因组，其相应序列被分成具有最小重叠长度的部分（即读段），分别计算每个部分的后缀数组，最后将所有部分计算的数组合并在一起成为单个数组。我们研究了不同读段/重叠长度对后缀数组构造算法运行时间的影响，并得出结论：最小重叠长度应等于相邻部分之间最长公共前缀的平均长度©2022作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍随着测序技术的不断进步，测序成本不断降低，测序片段长度和测序基因组数量不断增加。开发了三代测序机，每代的特征在于一组属性，例如产生的数据量（通量）、片段/读段长度、测序成本和所得数据的准确性一些代产生了具有成本效益的准确的高通量数据，并牺牲了读取序列的长度其他技术读取许多基因组应用所需的一长段测序数据，如研究复杂的结构变异和重复区域，但数据精度不高*通讯作者：Mansoura大学计算机与信息学院计算机科学系，P.O.信箱：35516，曼苏拉，埃及。电子邮件地址：sarah_almetwally4@mans.edu.eg（新加坡）El-Metwally）。沙特国王大学负责同行审查（Goodwin等人，2016; Bansal和Boucher，2019; Amarasinghe等人， 2020年）。短读段测序市场由Illumina机器主导，例如：MiSeq、HiSeq、NextSeq、NovaSeq和来自Thermo Fisher Ion Torrent公司的其他长读段测序技术主要由两家公司Pacific Biosciences（PacBio）和Oxford Nanopore Technologies（ONT）主导，这两家公司依赖于单分子实时技术表1显示了由当今领先测序市场的三家公司产生的测序数据的主要属性（表1）。DNA/RNA序列的长长度阅读段已被广泛用于解决计算生物学和生物信息学领域面临的许多计算挑战，例如基因组/转录组作图、组装、解析更复杂的结构变异和重复区域（Amarasinghe等人， 2020年）。大多数下游数据分析流程从将测序数据映射到参考基因组开始，映射过程的质量受到映射软件及其设置参数的影响（Alkhateeb和Rueda，2017）。大多数映射程序依赖于基因组/读段索引步骤，以便快速有效地映射读段。基因组/读段索引阶段通过构建一些https://doi.org/10.1016/j.jksuci.2022.04.0151319-1578/©2022作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comZ. Rabea，S. El-Metwally，S. Elmougy等人沙特国王大学学报4660ð ÞðÞð Þ表1三家领先的测序公司生产的测序数据的主要特征 *。公司测序方法读取长度错误率%单位：GB/运行测序机示例Illumina合成测序100百分之零点一200–600MiSeq、HiSeq、NovaSeqPacific Biosciences合成测序（SMRT技术）105-15%10–20续集II，RSII，续集Oxford Nanopore Technologies纳米孔测序高达1000 kb5-20%5–10MinION、GridION、异丙嗪* 表格改编自参考文献（Bansal和Boucher，2019）。有 助 于 搜 索 和 查 询 不 同 基 因 组 间 隔 的 辅 助 数 据 结 构 Burrows-Wheeler变换（BWT）代表了用于索引和压缩不同类型数据的许多算法和数据结构的基础。基因组数据的大多数流行映射算法依赖于BWT，因为它在索引和查询基因组区域方面的效率（Mrs. 2008，Keel和Snelling，2018; Daykin等人， 2021年）。基于BWT映射的算法开始于通过计算从参考序列采样的一组子串的BWT来这些子字符串以一种允许快速读取、搜索和匹配的方式排序和索引。计算非常长的序列和大量序列集合的BWT在计算上是昂贵的，并且存在许多方 法 来 克 服 在 这 些 场 景 中构建BWT的限制（ Cox 等 人 ， 2012;Cenzato and Lipták，2022）.后缀数组是一种有效的构造BWT的方法，它通过从基因组序列中提取一组有序的后缀来生成相应的索引。后缀数组将基因组编码为对应于按字典顺序排序的后缀集合的排序索引的序列在构造后缀数组时，总是要在时间和空间后缀数组的一些未压缩实现允许快速模式搜索，但代价是生成不适合任何计算机内存的庞大索引数据结构。其他压缩后缀数组技术生成了一个空间有效的数据结构，搜索时间慢最长共同前缀（LongestCommonPrefix，LCP）是一种辅助数据结构，当查询特定序列的后缀数组时，LCP可以与后缀数组相结合，通过搜索共同的基因区域来提高检索时间LCP在后缀数组中的相邻排序后缀之间存储共享子串的长度，并允许对公共序列前缀进行分层搜索（Shrestha等人，2014; Wu，2016）。大多数后缀数组构造算法考虑的是整数字母，而没有利用特殊类型的固定大小的，如DNA字母。我们的算法是优化的DNA的四个大小的字母表，是有效的算法相比，用于一般和整数为基础的。本文分为以下几个部分：第1节提供了以前的后缀数组构造方法的背景，第2节描述了四种大小的DNA字母表的后缀数组构造算法，第3节解释了所提出的方法的用例示例，第4节分析了算法性能和计算挑战，第5节讨论了实验设置和测试数据集，第6节总结了我们的论文，突出了主要结果和贡献。2. 背景生物信息学家的日常活动之一是将一组测序读数映射到完整的参考基因组序列。基因组索引是任何映射管道的第一步，高效的数据结构用于构建高效的基因组索引。用于构建基因组索引的最知名的数据结构之一是后缀数组。后缀数组将基因组编码为对应于字典图形排序的后缀集合的排序索引的序列。长度为T的文本的后缀数组n可以通过构建后缀树并对其进行遍历来构造，这种方法需要O n时间（ McCreight ， 1976;Farach-Colton ， 1997; Farach-Colton 等 人 ，2000年）。其他算法需要 O nlogn时间而不使用后缀树（ ManberandMyers 1993）。一些工作报告说，通过递归分而治之的方法，可以在 O n 时 间 内 直 接 构造 后 缀 数 组 （ Kärkkäinen 和 Sanders ， 2003年;Kim等人，2003; Ko和Aluru，2003; Hon等人，2009年;肯帕和Kociumaka，2021）。分而治之的方法开始于将提取后缀的集合分成两组，并且每个算法在拆分后缀的方式上不同。如果后缀是偶数或奇数，则根据它们的索引来划分后缀。其他算法基于模运算来划分后缀。第一组后缀将用于递归地构造后缀数组的一部分。后缀数组的构造部分将直接用于构造后缀数组的其余值，最后这两个部分以正确的顺序合并。后缀划分的奇/偶方法依赖于将后缀划分为奇和偶，这取决于它们在文本中的起始索引，旨在实现O（n）的运行时间（Farach-Colton等人，2000年; Kim例如，2003年）。在偏斜算法方法中，基于模式操作将后缀索引分成两组（即，后缀索引mod 3等于或不等于0）（Kärkkäinen和Sanders，2003年）。其他方法将后缀分为L型/S型后缀。后缀划分的偏斜算法与其他方法相比具有更快的一致性，而奇/偶方法具有更快的后缀划分和更少的递归调用操作。后缀数组构造算法面临着许多挑战，例如构造时间的成本，这意味着枚举所有后缀的成本这还包括递归方法中此外，用于存储中间计算值和最终后缀数组值所需的存储空间是另一个主要挑战。当索引数据结构的大小超过可用的内部存储器时，一些算法利用外部存储器，并且这将减慢数据检索任务，因为大部分访问时间将由盘I/O操作支配（Louza等人，2017 a，b，c; Egidi等人，2019; Lao等人， 2021年）。表2总结了后缀数组构造的一些方法，包括它们的属性和内存/时间限制。大多数提出的后缀数组构造算法没有考虑到当文本从固定大小的字母表中提取时的特殊情况，例如四个大小的DNA alpha- bets。对于有限大小的字母表，后缀数组的构造方法将是简单、快速的，并且省略了操作整数和一般字母表的复杂性我们的算法针对DNA的四个大小字母，并构造相应的后缀数组。3. DNA字母表后缀数组构造算法我们的算法利用了仅包含四个字母{A，C，G，T}的有限大小DNA字母表的性质，并利用它们的Z. Rabea，S. El-Metwally，S. Elmougy等人沙特国王大学学报4661-----表2比较几种后缀数组构造方法。Pang Ko和SrinivasAluruJuha Kärkkäinen 和 PeterSanders提出的算法SA是通过根据后缀类型（L型或S型）再次划分每个部分来递归地计算的。.最后的后缀数组是通过对序列的每个部分的部分构造的后缀数组进行排序和合并来计算的。● 后缀数组是通过提取和排序从索引i mod 3- 0开始的后缀来构造的。第一步中的部分构造的后缀数组用于构造和排序后缀数组中对应于其他后缀的剩余部分。合并这两个部分以构造最终的后缀数组。O（N）O（N）20032006（Kärkkäinen和Sanders，2003年;Kärkkäinen等人，（2006年）基于诱导排序的后缀数组构造D-关键子串（SA-DS）基于K字工作空间的后缀数组构造算法（SACA-K）● 后缀数组是通过提取最左边的S型（LMS）子串对应的后缀来构造的。部分构造的后缀数组用于基于分治方法计算其他值，并使用桶排序单独排序● 后缀数组是通过提取固定长度的d-临界子串对应的后缀来构造的。部分构造的后缀数组用于基于分治方法计算其他值，并使用基数排序单独排序● 后缀数组是通过从序列中提取LMS子串，对它们进行排序并将每个子串替换为整数来构造的以生成其压缩版本。通过合并为每个部分生成的各个数组（即，LMS子串）的序列。O（Nlog N）O（N） 2009（Nong等人，（2009年）O（Nlog N）O（N） 2011（Ge等人，（2011年）N log K + N log N + KO（N）2013（Nong，2013）通用版本SACA-K（gSACA-K）● 它依赖于SACA-K，并引入了最长公共前缀（LCP）数组值的计算来构造最终的后缀数组。5 N + O（1），如果N 231 bp9 N + O（1）否则O（N） 2017（Louza等人，2017年a、b）* 记忆复杂度由两个参数定义，N：基因组长度，K：字母表大小。** 时间复杂度在参数N中定义，参数N是基因组长度。字典顺序，使得对应于以A开始的后缀的索引总是在最终构造的后缀数组中位于任何其他计算的后缀之前。因此，后缀以C开头，然后后缀以G开头，最后后缀以T. 我们将从对应于被索引序列长度的值开始递增地构造后缀数组，并基于我们只有以A，C，G和T开头的后缀的事实填充其他值我们构造的后缀数组的第一个值构造的后缀数组中的第二第三组值是从所有以C开头的后缀中计算出来的，然后第四组是从以G开头的后缀中计算出来的，最后一组是从以T开头的后缀中计算出来的（见图2）。①的人。对于以特定的DNA α- bet开始的每一组后缀，内部排序算法应该通过检查字母表之后的下一个字符来进行，以便将后缀保持在词典编纂顺序中。提出了一种构造DNA字母后缀数组的算法，该算法依赖于DNA序列有A、C、G和T四个字母对于每个DNA字母表，我们将构建后缀数组的一部分，对应于以该字母表开始的后缀，对它们进行内部排序，并提供该部分的最终排序版本，以将其直接与其他DNA字母表的自动计算的版本一起附加。有两个方法在我们提出的算法中起着关键作用：第一个方法是SA_char从DNA字母表（即A、C、G或T）中提取，第二个方法find_index（x，y）为每个DNA字母表调用，并返回与该字母表在被索引序列中的所有出现对应的所有索引该方法将返回所有索引作为一对值x和y，其中x等于1，如果该方法是第一次调用每个DNA字母表（即从序列中提取的每个后缀中的第一个字符），y是该后缀在序列中以该字母表开始假设我们正在调用一个方法find_index（x，y）for Aalphabet，并且x等于1，该方法返回一组索引，对应于序列中以字母A开头的所有后缀如果对于相同的A字母表，x等于2，则该方法检查A字符之后的所有字符，并返回对应于序列等等。x的值表示可以从特定的DNA alpha- bet开始通过其搜索策略其主要目的是建立后缀数组的一部分，对应于后缀开始的A，并附加计算部分后缀数组的第一个元素，这是序列的长度然后，构建与以C开始的后缀相对应的另一部分，并将其附加到先前计算的部分，依此类推，直到所有DNA字母都被使用和处理。假设下一个计算的部分将是以G开头的后缀，那么算法将调用方法find_index（1，y）来查找序列中所有出现的G。对于G在序列中作为对（1，y）的每次出现构建方法算法记忆 *时间 *年参考文献算法由● 序列根据后缀classi分为两部分-O（N）O（N）2003（Ko and Aluru 2003）Z. Rabea，S. El-Metwally，S. Elmougy等人沙特国王大学学报4662-¼---- --ð0 Þ ¼ ½ ]四分之一 ] 的一种-Fig. 1. 使用所提出的DNA字母表算法为序列“ACGTTGTCAACTGTTGCACGTAAACGTTAA $”构建后缀数组阵列或不。这个步骤意味着检查G字母表后面的下一个字符，如果z已经在后缀数组中，则其对应的x值将被更改为数组中z的索引，所有具有正x值的对都根据x进行排序，并且它们对应的y值被附加到后缀数组的构造部分。x的最终正值将是从处理的对（x，y）中的每个对应y值开始的后缀的最长共同前缀的长度，并且因此在将它们的对应y值添加到后缀数组的构造部分如果在后缀数组中找不到z，这意味着x值为负，则算法将根据序列中位置z处出现的字符A、C、G或T来划分对。这个步骤意味着根据序列的固定大小的字母表构建一个最多有四个分支的内部树结构根据后缀数组先前创建的部分，可以最小化树分支在我们的场景中，计算所有带有A和C的后缀对于后缀数组的构造部分中的z的每个不出现，x的负值将递减，这意味着搜索整个序列尝试不同的深度（即，当前字符之后的两个/三个/四个字符等）。具有负x值的对将被传递到算法的下一轮，以便基于每一轮中后缀数组的更新的计算部分将它们的负值改变为它们对应的最长公共前缀（参见图2）。2）的情况。提出的后缀数组构造算法在生物信息学中有许多应用，并且可以通过用U替换T字母表而容易地扩展到RNA字母表第一个也是最重要的应用是基因组和转录组索引，允许快速查询操作。此外，该算法可以用于模式发现程序，该程序搜索参考基因组/转录组的特定模式（即测序读数、基因等）。或疾病生物标志物。此外，该算法可以被合并到一个完整的映射程序，并准确地找到测序数据在参考基因组/转录组中的最佳可能位置。许多生物信息学下游数据分析依赖于精确的映射信息来执行不同的任务，例如计算基因表达水平和变异识别。4. 用例示例假设将为长度为N29个字符（即从零偏移开始的N1）的DNA序列S =ACGTTGTCAACTGTTGCACGTAAACGTTAA构造后缀数组。让这个符号$是序列的结束字符，在词汇上比任何其他DNA字母表都小。根据所提出的算法，最终构造的后缀数组将是对应于字母表{$，A，C，G，T}的部分构造部分的并集。ACGTTGTCAACTGTTGCACGTAAACGTTAASA¼SA通道。00[SAcha r.0A0[SAcha r.0C0C[SAchar.0G0[SAchar.0吨 0吨SA字符0N30，这是从零偏移开始的DNA序列中符号$的索引。该算法通过调用序列中字母表A的方法find_index（ 1，y）开始，该方法返回（1，y）对：（1，y）= {（1，0），（1，8），（1，9），（1，17），（1，21），（1，22），（1，23），（1，28），（1，29）}。返回的对应该根据y值进行排序，我们在python中使用了一个内置的sort方法，该方法依赖于Timsort算法来完成这项任务。所有y值表示S中所有A的索引。相应的z值将是：{1，9，10，18，22，23，24，29，30}。SA¼½30]在suf- fix数组的已构造部分中找到的唯一z值是30，它对应于$的索引。对应于找到的z的对x，y的值是（1，29），并且该值将被改变为（0，29），因为z的索引是零Z. Rabea，S. El-Metwally，S. Elmougy等人沙特国王大学学报4663--------图二. 所提出的DNA字母后缀数组构造算法的流程图。在后缀数组的已构造部分中。y值29将被附加到数组SA，并且（0，29）对将从下一轮算法计算中移除。SA¼½30;29]该算法将继续对集：（1，y）={（1，0），（1，8），（1，9），（1，17），（1，21），（1，22），（1，23），（1，28）}，其具有对应的z值：{1，9，10，18、22、23、24、29}。在SA中找到的唯一z值是29，其对应值为29。响应对将被改变为（1，28），从算法计算中移除，并且值28被附加到SA。SA¼½30;29;28]该算法将继续对集：（1，y）={（1，0），（1，8），（1，9），（1，17），（1，21），（1，22），（1，23）}，其具有对应的z值：{1，9，10，18，22，23，24}。在SA中并没有找到所有的z值，因此该算法根据序列S中 z个位置处出现的字符对集合进行Z. Rabea，S. El-Metwally，S. Elmougy等人沙特国王大学学报4664--------[1/2]ð ÞðÞ图三. 序列字符出现在不同的z位置。根据图 3中，将对的集合划分为对应于出现在不同z位置处的两个字符（即，A和C）的两个子集。x的值将递减1，以探索另一个深度（即，下一个字符出现-在已经检查的字符之后）。这两个子集是：{{（2，8），（2，21），（2，22）}，{（2，0），（2，9），（2，17），（2，23）}}假设我们现在关注第一个子集{（2，8），（2，21），（2，22）}。对应的z值为{10，23，24}，在中未找到z值。SA30; 29; 28 .因此，算法将划分对并将x的值递减为：{{（3，21）}，{（3，8），（3，22）}}。取第一个子集{（3，21）}，对应的z值：{24}，这在SA中找不到，并且没有更多的对要划分，因此算法将把y值21附加到构造的后缀数组，并且x的值将被改变为3，因为这是对的这个子集（即，树分支）可以达到的最大算法深度。SA¼½30;29;28;21]该算法将继续与其他子集值一起工作，如先前所解释的，并根据图2中所示的流程图。该算法的工作场景可以表示为一个树结构，如图1所示。 四、我们应该清楚地提到，后缀数组值是从文本的排序后缀计算的，并且基因组文本是仅具有四个字母A、C、G和T的DNA，因此基因组构建的后缀数组的值将对应于以DNA字母表开始并按字典顺序排序的后缀。此外，所提出的算法通过从最小的词典编纂字符$开始，然后计算对应于DNA字母表中的下一个最小字符A的后缀数组值的部分，后缀数组构造算法显然依赖于DNA字母表的字典性质，以便计算后缀。固定数组值准确和正确（图。 5）。5. 算法分析和挑战有两种方法在所提出的后缀数组构造算法（算法1）中起着关键作用，图五. E-coli的后缀数组构造、合并和总运行时间参考基因组被划分为长度为100 bp和不同重叠大小的读段。算法2定义的find_index和算法3定义的SA_char算法1的运行时间主要由两条线6和7决定方法find_index（第6行）的运行时间为O N，其中N是基因组长度。方法SA_char（第7行）的运行时间为Onk，其中k2fA;C;G;Tg，nk是参考基因组中字母表k由于我们的算法是针对DNA字母表设计的，所以我们的算法的最长运行时间用于构造与以'A'开头的后缀对应的后缀数组的一部分，同样，对nk个索引排序的运行时间是O nk lognk，这与python Timsort算法相对应。最不图四、树结构中对应后缀数组的构造算法为字母A和序列S = ACGTTGTCAACTGTTGCACGTAAACGTTAA$.Z. Rabea，S. El-Metwally，S. Elmougy等人沙特国王大学学报4665¼●●ð Þ← ½]¼ þ← j jð-Þ●←¼¼Þ¼ --一种ð-ð þÞ Þð-ð þÞ Þð-ð þÞ Þð-ð þÞ Þ我们的算法的运行时间用于构造suf的一部分修复与以'T'开头的后缀对应的数组，与字母表“T”在序列中出现的次数有关。如所指出的nk N，所以所提出的后缀数组构造算法的总运行时间是O N。如果N非常大（即，大尺寸基因组），则基因组可以被划分为部分，并且计算每个部分的后缀阵列，并且因此合并单独构建的后缀阵列。为了正确有效地构造后缀数组，我们注意到在基因组分割操作中需要保留一个最小重叠长度。重叠区域在后缀数组计算中被考虑一次，在最终构造的后缀数组中不重复其对应的值。假设长度为N的基因组被分成长度为L的子串，这些子串的最小重叠长度等于l。整个基因组由M N=L个子串覆盖。 在为覆盖一个基因组的M个子串集合构造后缀数组的算法中，有两个因素在算法的运行时间中起着关键作用：子串长度（L）和最小重叠长度（l）。在基因组的情况下，我们的算法的运行时间由一组M个子串表示，每个子串的长度为L，并且所有子串具有最小重叠长度l将是O<$M ω <$L<$l<$$>，每个子串具有后缀数组构造算法等于O<$L <$l，并且合并算法的运行时间将是O<$N <$。算法1：DNA字母的后缀数组构造输入：参考基因组：G输出量：● 后缀数组：SA1：G G002：N G3：SA4：将N添加到SA5：对于每个k，在第六章：通过find_index返回基因组中k法7：通过方法返回后缀数组SA_k的一部分，对应于kSA_char8：将SA_k附加到SA9：结束于算法2：find_index输入：参考基因组：G输出量：F_index：G中k字母表的所有索引作为一对值x和y返回。1：N← jGj2：i←03：F_index← ½]4：WhileiN do：<第五章：如果G½i]k：6：将一对1;i附加到F_index7：结束If第8章：结束算法3：SA_char输入：● 参考基因组：GF_index：G中k字母表的所有索引作为一对值x和y返回。后缀数组的初始值：SA输出量：● 后缀数组的最终值：SA1：x←F_inde x[0][0]，y←F_inde x[0][1]，n1←| F_inde x|、标志←真，F_索引2← ½]。2：F_A <$½]，F_C<$½]，F_G<$½]，F_T <$½]。3：如果（n11：4：将y附加到SA5：结束，如果6：WhileFlag do：7：对于F_index中的每个对（x，y），8：z¼y-x9：如果是2，则为：10：indx← SA中z的索引11：创建新列表F_index 2并添加对（indx，y）12：从F_index第13章：结束十四日：端十五：n2←| F_index 2|十六日：如果（n217：对列表进行排序F_index218：对于F_index2中的每个对（x，y），19：将y附加到SA第20章：一夜情21：否则：第22章：一夜情二十三：End If第24章：最后一次25：对于F_index中的每个对（x，y），26：z y x二十七日：如果（G[z]=第28章：一个女人1;y到F_A29：否则如果（G[z]=30：添加一对x1;y到F_C31：否则如果（G[z]=第32章：一个女人1;y到F_G33：其他第34章：一个女人1;y到F_T35：结束，如果第36章：一夜情37：nA←| F_A|，nC←| F_C|，nG←| F_G|，nT←| F_T|38：如果（nA39：SA_char（F_A）40：如果（nC41：SA_char（F_C）42：如果（nG43：SA_char（F_G）44：如果（nT45：SA_char（F_T）第46章：一夜情6. 实验结果使用具有不同长度的三个真实数据集评估DNA字母的后缀阵列构造算法，如表3所示。第一个数据集是一个完整的参考基因组，●●●Z. Rabea，S. El-Metwally，S. Elmougy等人沙特国王大学学报4666表3特征数据集用于后缀数组构造算法的评价。当读段长度大于150 bp且小于1100 bp时，产生计算（图1）。6）。当重叠大小减少到50 bp时（图1）。 7），最佳运行-基因组名称长度NCBI参考序列读取时间由范围从100 bp到650 bp的读取长度产生。后缀数组构造算法工作效率高大肠埃希菌K-12菌株MG 1655人GRCh38.p13的1号染色体人GRCh38.p13的21号染色体4，641，652 bp NC_000913.3248，956，422 bpNC_000001.1146，709，983 bp NC_000021.9并且如果重叠长度等于LCP的平均值，则该算法是正确的，并且当重叠大小增加时，该算法可以使用更长的读取长度。对于长度分别等于248，956，422 bp和46，709，983 bp的智人GRCh38.p13的染色体1和21每个染色体被分成一组读段（即子串），并且我们测试了不同的长度以鉴定染色体的长度。含有一条染色体的大肠杆菌4，641，652 bp第二个数据集是长度为248，956，422bp的智人GRCh38.p13参考基因组的1号染色体，第三个数据集是长度为46，709，983bp的21号染色体。在我们的算法被评估之前，从任何序列中移除间隙字母表（即N或n）。所有实验都在具有Win-Xeon 10 Pro版本21 H1 64位操作系统的工作站上进行，该操作系统使用Intel（R）Xeon（R）CPU E5-1620 v2、3.70 GHz处理器，该处理器具有256个L1高速缓存、1MB L2高速缓存、10 MB L3高速缓存、64 GB RAM和128 GBSDD硬盘.对于长度为4，641，652 bp的大肠杆菌参考基因组，基因组被分成多个部分（即读段），每个部分的长度为100 bp，加上特定的重叠值;我们测试了许多重叠大小（范围从10 bp到10，000 bp），以便为我们的后缀阵列构建方法找到最佳结果。我们发现最佳重叠长度等于大肠杆菌基因组的最长共同前缀LCP中包含的值的平均长度后缀阵列的正确和真实计算值是由长度为200 bp至600 bp的读段覆盖的基因组和范围为50 bp至100 bp的重叠大小（相当于LCP中计算的大肠杆菌参考基因组值的平均长度）产生的为了研究改变覆盖基因组的读段的长度对后缀阵列值的计算的影响，我们测试了具有不同长度的读段，并且如先前报道的固定重叠大小等于100 bp后缀数组的最佳运行时间见图6。用于大肠杆菌参考基因组的后缀阵列构建、合并和总运行时间，所述大肠杆菌参考基因组被划分为具有不同大小和100 bp重叠长度的读段。最佳读取大小。所有读段具有100 bp的固定重叠大小。对于Chr. 1，当覆盖染色体序列的平均读取长度为600-1100 bp时，得到最佳运行时间对于Chr. 如图21所示，当覆盖染色体序列的平均读取长度为200-1100 bp时，得到最佳运行时间（图21）。 9）。由于我们提出的后缀阵列构建算法主要在基因组索引阶段工作，并且我们计划在未来将其功能扩展到完整的映射软件中，因此我们用当前最先 进程 序的索 引阶 段评 估我们 的索 引步骤 ，例 如BWA （Li ，2013），eGSA（Louzaet al.，2013）和lordfast（Haghshenas等人，2019年）的报告。我们在我们的基准实验中使用大肠杆菌参考基因组，评估结果显示在表4中。BWA和lordfast依赖于Burrows-Wheeler变换和FM索引进行基因组索引，而eGSA利用外部存储器来构建对应于参考基因组的后缀阵列的广义版本。为了比较我们提出的算法在基因组索引阶段的正确性，我们将我们的方法产生的Burrows-Wheeler变换（BWT）与eGSA产生的Burrows-Wheeler变换（BWT）进行了比较，并且它们对于两个数据集是相同的。eGSA是唯一一个输出BWT文本版本的对齐工具，而其他工具则以二进制格式生成我们应该注意到，所有的基准测试工具都是完全自动化的对齐器，它们并行化了后缀数组构造阶段和对齐过程。而且，他们没有保存任何中间结果，因为它们直接用作对准过程中下一阶段的输入。eGSA和我们提出的见图7。用于大肠杆菌参考基因组的后缀阵列构建、合并和总运行时间，所述大肠杆菌参考基因组被划分为具有不同大小和50 bp重叠长度的读段。Z. Rabea，S. El-Metwally，S. Elmougy等人沙特国王大学学报4667见图8。智人1号染色体的后缀阵列构建、合并和总运行时间，该染色体被划分为具有不同大小和100 bp重叠长度的读段。见图9。智人21号染色体的后缀阵列构建、合并和总运行时间，该染色体被划分为具有不同大小和100 bp重叠长度的读段。方法与其他工具相比具有较长的执行运行时间，因为它们生成的是BWT的文本版本。为了证明所提出的DNA字母表后缀数组构造算法的正确性，生成了后缀数组和BWT的文本文件，并根据磁盘写操作的缓慢性对算法的运行时间进行了控制。此外，基准测试工具正在利用并行方法以加快其后缀数组构建过程，而所提出的算法被设计为所提出的想法的概念证明，并且我们计划在未来扩展其功能以执行序列比对并并行化其操作。为了加快后缀数组的构造过程，可以使用文献中的许多方法，例如通过消息传递接口MPI使用分布式内存的并行计算机架构，或者使 用 具 有 多 个 内 核 和 GPU 的 单 机 （ Kulla 和 Sanders ， 2007;Osipov，2012; Shukhrov，2019）。我们的算法可以受益于分布式系统架构或单机多核，通过将长输入参考基因组分成部分，这些部分可以均匀分布在可用的处理器数量上。每个处理器具有其自己的基因组部分以构建其对应的后缀数组，并且仅交换消息/值将发生在具有基因组的相邻部分的处理器之间。每个处理器具有其自己的后缀数组的 部 分 构 造 部 分 ， 并 且 这 些 部 分 构 造 部 分 也 可 以 并 行 排 序（Futamura等人，2001; Lao等人，2018）并合并以产生对应于输入参考基因组的后缀阵列的单个构建版本。7. 结论大多数下游基因组数据分析管道开始于将测序数据映射到索引的参考基因组。用于构建基因组索引的最知名的数据结构之一是后缀数组。有许多方法可以有效地构造后缀数组，大多数方法忽略了从固定大小的字母表（如四个大小的DNA字母表）中提取文本的特殊情况所提出的用于构造DNA字母表的后缀阵列的算法依赖于仅具有四个字母的DNA字母表的思想，这四个字母是A、C、G和T，具有预定义的词汇排序。后缀数组中的第一个值将是被索引的基因组的长度然后，对于每个DNA alpha- bet，我们将构造后缀数组的一部分，对应于以该字母表开始的后缀，对它们进行内部排序，并提供该部分的最终排序版本，以将其直接与先前计算的其他DNA字母表的后缀一起部分计算的后缀数组的一些步骤可以并行化，以加快计算速度此外，将所提出的算法集成到完全作图程序中将是我们的下一步，以便将我们的实验结果与基因组领域中可用的表4BWA、eGSA和lordfast比对工具对所提出的后缀数组构造算法的评估结果工具Prog. 语言命令行运行时间参考文献BWAC++bwa index ref.fasta9.831（Li，2013）eGSAC++./ egsa -b参考fasta15（Louza等人， 2013年度）洛德法斯特C++./ lordfast5.68（Haghshenas等人， 2019年度）该方法Pythonpython Suffix.py ref.fasta121本文Z. Rabea，S. El-Metwally，S. Elmougy等人沙特国王大学学报4668竞争利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作。引用Escheroh，D.，贝尔，T.，慕克吉，A.，2008. Burrows-Wheeler变换：数据压缩、后缀数组和模式匹配。Springer Science& BusinessMedia.Alkhateeb，A.，鲁埃达湖2017.下一代测序数据预处理方法。 J. Comput. Biol.24（8），746-755。Amarasinghe，S.L.，Su，S.，Dong，X.，（中国科学院，中国地质研究所，北京，2003）扎皮亚湖，里奇法医Gouil，Q.，2020.长读段测序数据分析的机遇和挑战。Genome Biol.21（1）. https://doi.org/10.1186/s13059-020-1935-5网站。班萨尔，V.，Boucher，C.，2019年。 测序技术和分析：我们在哪里，我们要去哪里？iScience 18，37-41.Cenzato，D.，Z. 利普塔克2022年对字符串集合的BWT变体的理论和实验分析arXiv预印本arXiv：2202.13235。考克斯，A.J.，Bauer，M.J.，Jakobi，T.，Rosone，G.，2012.用Burrows-Wheeler变换大规模压缩基因组序列数据库。生物信息学28（11），1415-1419。Daykin，J.W.，Mhaskar，N.，史密斯，W.，2021.后缀数组、Burrows-Wheeler变换和V阶FM指数的计算。理论计算。Sci. 880，82-96。埃吉迪湖佛罗里达州卢扎，曼齐尼湾，例如，2019.外部存储器BWT和LCP计算序列集合与应用程序。算法分子Biol.14，6. https://doi.org/10.1186/s13015-019-0140-0网站。Farach-Colton，M.， 1997. 大字母表的最优后缀树构造。FOCS。Farach-Colton，M.，Ferragina