{"paper_id":"5e474270-a1ed-416f-b67e-bdf5ed54de92","body_text":"Journal Title Here, 2023, pp. 1–10\ndoi: DOI HERE\nAdvance Access Publication Date: Day Month Year\nPaper\nPAPER\nARYANA-BS: Context-Aware Alignment of\nBisulfite-Sequencing Reads\nHassan Nikaein,1 Ali Sharifi-Zarchi,1,∗ Afsoon Afzal,2 Saeedeh Ezzati,1 Farzane Rasti,1\nHamidreza Chitsaz3 and Govindarajan Kunde-Ramamoorthy 4\n1Department of Computer Engineering, Sharif University of Technology, Tehran, Iran, 2School of Computer Science, Carnegie Mellon\nUniversity, Pittsburgh, USA, 3AutoX technologies and 4The Jackson Laboratory, Bar Harbor, USA\n∗Corresponding author. sharifi@sharif.edu\nFOR PUBLISHER ONLY Received on Date Month Year; revised on Date Month Year; accepted on Date Month Year\nAbstract\nMotivation: DNA methylation plays a crucial role in biological processes, including imprinting, development,\ninflammation, and several disorders, such as cancer. Bisulfite sequencing (BS) is the gold standard for single-base\nresolution in measuring DNA methylation. This process involves treating genomic DNA with sodium bisulfite, followed by\npolymerase chain reaction (PCR), converting unmethylated cytosines to thymines (C to T) and guanines to adenines (G\nto A). However, aligning reads obtained through next-generation sequencing (NGS) of the converted DNA is challenging\ndue to the high number of mismatches caused by these conversions.\nVarious BS aligners aim to simplify BS read alignment to conventional DNA alignment by modifying the reference genome\nand/or reads. Methods include three-letter alignment and wild-card alignment, each with its limitations.\nThis work introduces a novel BS aligner, ARYANA-BS, which departs from conventional DNA aligners by considering base\nalterations in BS reads within its alignment engine. Leveraging well-established DNA methylation patterns in different\ngenomic contexts, ARYANA-BS generates five indexes from the reference, aligns each read to all indexes, and selects\nthe hit with the minimum penalty. To further enhance alignment accuracy, an optional EM step has been developed,\nincorporating methylation probability information in the decision-making process for the index with the minimum penalty\nfor each read. The presented approach seeks to improve the accuracy of BS read alignment by accounting for the intricacies\nof DNA methylation patterns in diverse genomic contexts. Results: Our experimental results, based on both simulated\nand real data, demonstrate that ARYANA-BS achieves state-of-the-art accuracy while maintaining competitive speed\nand memory usage.\nAvailability: The source code of ARYANA and ARYANA-BS, the read simulator for both normal and bisulfite-treated\nreads, SAM file analyzer which is used for post processing of the alignment penalties, and test procedures for benchmarking\ndifferent aligners using simulated and real data, are publicly available in https://github.com/hnikaein/aryana.\nContact: sharifi@sharif.edu\nSupplementary information: Supplementary data are available at Journal Name online.\nKey words: DNA methylation, bisulfite sequencing, alignment, CpG island\nIntroduction\nDNA methylation is the earliest recognized epigenetic mechanism that is found primarily in vertebrates. This process involves the\nattachment of a methyl group to carbon 5 of genomic cytosine, resulting in 5-methylcytosine [36]. DNA methylation plays a crucial\nrole in a multitude of biological processes, including but not limited to imprinting, differentiation, development, inflammation,\ntranscriptional silencing, and various diseases such as cancer [35]. Therefore, analyzing and evaluating methylation data can\nprovide extensive information about the regulatory mechanisms of vertebrate cellular life.\nMost methylated cytosines are found adjacent to a guanine nucleotide, forming a CpG site. However, cytosines in the forms of\nCpA, CpT, and CpC are typically not methylated [36]. Many regions of a vertebrate genome lack CpGs due to the deamination of\nmethylated cytosines, which convert them to uracil. During DNA replication, uracil is replaced by thymine, resulting in a C to T\nconversion [14]. Specific regions in the vertebrate genome, called CpG islands, have a higher ratio of CpGs and GC content than\nother genomic regions. CpG islands are usually hypomethylated (i.e., having lower DNA methylation levels), while isolated CpGs\nlocated outside of CpG islands tend to be hypermethylated (i.e., having higher DNA methylation levels) [36].\n© The Author 2023. Published by Oxford University Press. All rights reserved. For permissions, please e-mail:\njournals.permissions@oup.com\n1\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\n2 ARYANA-BS\nDenaturation\n5' 3'Watson A C T C G C G T C G G T G C A\n3' 5'Crick T G A G C G C A G C C A C G T\n3' 5'Crick T G A G C G C A G C C A C G T 5' 3'Watson A C T C G C G T C G G T G C A\nBisulfite\nTreatment\n3' 5'BSC T G A G C G U A G U U A C G T 5' 3'BSW A U T U G C G T U G G T G C A\nPCR\nAmplification\n5' 3'BSW A T T T G C G T T G G T G C A\n3' 5'BSWR T A A A C G C A A C C A C G T\n5' 3'BSCR A C T C G C A T C A A T G C A\n3' 5'BSC T G A G C G T A G T T A C G T\nC                    methylated cytosine\nC                unmethylated cytosine\nN                    changed nucleotide\nFig. 1. The bisulfite sequencing procedure. In the first step, an enzyme unwinds the DNA into Watson and Crick fragments. Then, during bisulfite\ntreatment, the unmethylated cytosines are converted to uracil. Furthermore, during PCR, all uracils are converted to thymines in the final step. This\nconversion converts the related Crick(Watson) nucleotide from guanine to adenine.\nSeveral experimental techniques are used to measure DNA methylation levels across the genome, including methyl-DNA\nimmunoprecipitation (MeDIP), methylation-sensitive restriction enzymes (MSREs), and bisulfite sequencing (BS) [20]. Among\nthese techniques, BS is widely used due to its ability to provide single-base resolution and high-throughput scale when used\nwith next-generation sequencing (NGS) technology. Treating genomic DNA with sodium bisulfite results in the deamination of\nunmethylated cytosines, which are converted to uracils. During polymerase chain reaction (PCR), uracils are replaced by thymines,\nresulting in a C to T conversion. Meanwhile, methylated cytosines remain unchanged. Using NGS, we can align reads to the\nreference genome and identify C to C versus C to T conversions to count the number of methylated versus unmethylated cytosines,\nrespectively.\nIt is important to note that the reverse complement strand obtained by PCR shows G to G versus G to A conversions in\npositions opposite to methylated versus unmethylated cytosines, respectively (Figure 1).\nDepending on the biological inquiry at hand, there are several sequencing methods available for profiling cytosine methylation\npatterns in DNA, including whole genome bisulfite sequencing (WGBS), reduced representation bisulfite sequencing (RRBS), and\ntargeted bisulfite sequencing. WGBS involves the treatment of the entire genomic DNA with sodium bisulfite, followed by PCR\namplification and sequencing, resulting in a comprehensive view of cytosine methylation patterns across the entire genome, albeit at\na higher NGS cost. In contrast, RRBS targets CpG-rich regions such as promoters and CpG islands by using specific methylation-\ninsensitive restriction enzymes, enabling the generation of more data at a lower NGS cost [23]. Lastly, targeted bisulfite sequencing\nis employed when we want to analyze the methylation status of a specific gene or genomic region.\nA major challenge associated with analyzing WGBS and RRBS data involves the alignment of NGS reads to the reference\ngenome. In conventional DNA short read aligners such as BWA [22], Bowtie2 [21], and others, all C to T and G to A conversions\nare interpreted as mismatches. Many of these aligners rely on a seed-and-extend strategy [31], which may not be effective in\nfinding exact matches (seed sequences) when mismatches occur frequently. Therefore, specific aligners are needed for the analysis\nof bisulfite sequencing reads.\nMany BS short read aligners use the primary strategy of adapting BS reads and/or the reference genome to enable conventional\nshort read aligners to align them without modification. However, two different methods have emerged to resolve the C to T\nconversions (G to A conversions can be resolved in a similar manner).\nThe first method is the three-letter alignment, which involves converting all Cs of both reference and reads to Ts, thereby\neliminating mismatches due to bisulfite C to T conversions and making it easy to use a conventional short-read aligner [10].\nBismark [18] produces two indices from the reference genome by converting Cs to Ts and Gs to As and then aligns the reads to\neach of them using the same conversions. This adaptation of the data, however, results in the loss of the distinctions between Cs\nand Ts in both reference and reads, and consequently, read Cs can be aligned to genomic Ts, which is not possible in bisulfite\nconversion. This information loss leads to multiple alignment hits across the reference at the same score, reducing the number of\nreads with a unique alignment position [4]. Some methods have extended this approach to introduce a two-letter alignment by\nsimultaneously converting Cs to Ts and Gs to As in both reference and reads [12], but this approach leads to even more information\nloss than the three-letter method.\nThe second method is wild-card alignment, which involves replacing all Cs of the reference with the wild-card letter Y, which\ncan stand for either C or T in IUPAC. In this way, Cs and Ts of the reads can be aligned to the reference Ys. BSMAP [38] uses\na hash table to record all k-mers in the reference genome and records all C-to-T variations of the reference k-mers to implement\nthe wild-card alignment. Unlike the three-letter alignment, the wild-card alignment does not result in information loss. However,\nit has a bias toward aligning reads from hypermethylated genomic regions better, as reads coming from such regions have more\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\nARYANA-BS 3\nCs, which can only be mapped to reference Ys. In hypomethylated regions, Cs diminish after C to T conversion, and Ts of a\nread can be aligned to both Ys and Ts of the reference, leading to nonunique alignment. Many downstream analyses, including\nthe estimation of the methylation ratio of each genomic cytosine, eliminate nonuniquely aligned reads. As a result, this method\nsuffers from a systematic overestimation of the methylation ratio, since reads from hypermethylated regions have a better chance\nof unique alignment [4].\nIn this article, we introduce ARYANA-BS, a novel short read aligner for bisulfite sequencing that builds upon our previous\nwork on the conventional short read aligner, ARYANA [11]. Unlike many existing methods that rely on adapting reads and/or\nreferences, ARYANA-BS incorporates specific treatments for BS reads during the alignment process. Specifically, we have enhanced\nthe methods for gap-filling, computing edit distance, and alignment score (penalty), considering the possible base conversions that\nmay occur due to bisulfite treatment, based on the distinct contexts in which they occur. These contexts include differentiating\nbetween CpG and non-CpG cytosines, as well as CpG island and non-CpG island regions. Additionally, we utilize five distinct\nindexes for optimizing the seed-finding procedure, as described in detail in the Methods section. Furthermore, we developed an\noptional EM step that leverages the methylation probability of each cytosine to improve the final alignment result.\nWe benchmarked ARYANA-BS, as well as several widely-used BS aligners, including Bismark [18], BSMAP [38], bwa-meth\n[27] (a three-letter aligner), BSBolt [9] (another three-letter aligner), and abismal [7] (a two-letter aligner), using both simulated\nand real data. We utilized a pair of simulators, one developed by us and another introduced in independent research, and found\nconsistent results. Additionally, we used real data that had previously been used in independent benchmarks of BS aligners. We\nprovide time, memory, and accuracy comparisons of the aligners, and show that ARYANA-BS outperforms the other aligners in\nterms of alignment accuracy on simulated and real data, while still maintaining competitive speed and memory usage.\nResults\nWe conducted a comparative analysis of ARYANA-BS against five other widely used WGBS aligners: BSMAP, Bismark, bwa-meth,\nBSBolt, and abismal. BSMAP was chosen for its acceptable results in prior studies, while Bismark is known for its effectiveness and\nwidespread use. bwa-meth is an adaptation of BWA mem, while BSBolt is a new aligner, and abismal employs a unique approach\nof two-letter mapping. The default configuration parameters were employed for all tools. The comparison was carried out using\nSAM file analyses, with hg38 as the reference and the CpG islands file obtained from http://hgdownload.cse.ucsc.edu/goldenpath/\nhg38/database/cpgIslandExt.txt.gz.\nIn the initial phase, we generated simulated bisulfite-treated reads from the hg38 genome using both the ARYANA and\nSHERMAN read simulators [1]. In the subsequent phase, we conducted an extensive evaluation of our algorithm using real data\nsourced from SRR3469520, which is available from the NCBI. This real-world dataset provided a valuable benchmark for assessing\nthe efficacy of our methodology. Finally, in the last phase of our investigation, we delved into the impact of incorporating an\nadditional expectation-maximization (EM) step on the outcomes generated by ARYANA-BS. This step was introduced to further\nrefine the results and explore potential enhancements to the algorithm’s efficacy.\nIt should be noted that although Bismark supports paired-end alignment, we encountered several unsuccessful attempts to run\nit on paired-end data, resulting in no output. Furthermore, BSMAP can only align reads that are 144 bp or shorter, rendering it\nunusable in some analyses.\nAll tools were employed in single-threaded mode, with an AMD Ryzen 5 3600X CPU and a maximum of 48 GB memory.\nsimulated data\nIn the initial stage, our objective is to compare ARYANA-BS with other tools based on simulated data. The data generated for\nthis purpose were simulated using both the ARYANA simulator and Sherman. We used the ARYANA simulator to generate both\n100 bp and 300 bp single-end and paired-end reads. For Sherman, we only generated 100 bp single-end reads. However, despite\nrunning for 163 hours, Sherman failed to generate any output for the simulation of 300 bp single-end reads.\nThe ARYANA simulator was developed to generate reads for regular sequencing as well as bisulfite sequencing. To simulate\nbisulfite sequencing, the simulator takes the reference genome as input and produces SNPs after loading the reference genome\ninto memory. During the read generation process, the simulator takes into account the insertion, deletion, and mismatch ratio\nprovided in the input. Moreover, the simulator generates reads from both the positive and negative strands. In the case of bisulfite\nsequencing, the simulator also incorporates the effects of negative strand and PCR in the output reads. These effects are based\non G-to-A and C-to-T conversions that are dependent on the C or G in the reference genome. The CpG islands from the input\nare utilized by the simulator to make bisulfite conversions based on the context of cytosines. The default methylation ratios for\nthe CpGs inside the CpG islands are set at 0.1, while outside the CpG islands the default is 0.9, and for the CpH, the default\nmethylation ratio is 0.01.\nThe primary aim of the first comparison is to evaluate the accuracy and performance of various tools. In the subsequent two\ncomparisons, we closely examine the effect of possible biases in the genomic context on the performance of the tools.\nComparison of Memory, Time, False Discovery Rate (FDR), and Correctly Mapped Reads Percentage\nIn this analysis, we evaluated the accuracy of the tools based on simulated reads. We generated 1,000,000 reads for each simulation\nand used the tools to align them with the reference genome. We used the ARYANA simulator for four simulations that differed\nin the length of reads and whether they were single-end or paired-end sequencing. The ARYANA simulator was configured to use\n4 million single-nucleotide polymorphisms (SNPs). Additionally, the Sherman simulator was used to simulate 100 base pair (bp)\nsingle-end reads.\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\n4 ARYANA-BS\nWe considered an alignment to be correct if the reported position by the tool for the alignment differed by no more than one\nbase pair from the actual position reported by the simulator. We also computed the FDR using the following formula:\nFDR = Count of incorrectly mapped reads\nCount of total mapped reads\nIn all simulation data generated by ARYANA and the Sherman simulator, ARYANA-BS outperformed all other tools in terms\nof the number of correctly mapped reads. However, BSMAP had comparable results in three simulations, but it only supports\nreads shorter than 145 bp, making it unsuitable for sequencers of larger read sizes.\nThe best whole-genome bisulfite sequencing (WGBS) aligner in terms of performance analyses was abismal, with the minimum\nruntime and memory usage of all tools. However, its accuracy was not acceptable. Bismark had better memory usage, but its\naccuracy was worse than that of any other tool. ARYANA-BS had comparable runtime to other tools, and in simulations with\nlonger read sizes, it was faster than others. Moreover, its memory usage stood at an average level, closely aligning with that of\nBSMAP.\nAlthough the FDR of ARYANA-BS was not as low as that of bwa-meth or BSBolt, we should work on reducing it. (see Figure\n2)\nIn Figure 3, we demonstrated that most of the reads aligned to the context-aware indexes instead of the original index and\nthree-letter indexes. This result highlights the importance of context-aware alignment in the improvements of ARYANA-BS.\nSingle Nucleotide Polymorphisms (SNPs) and Indel Rates\nIn Figure 4, we present a comparison of correctly mapped reads for simulated reads with varying SNP counts and different indel\nrates. This analysis showcases the efficacy of the tool in genomic change analyses, such as cancer analyses.\nIn the initial simulation, we simulated two sets of reads with SNP counts of 4 million and 40 million. Although this change has\na negligible impact on the tool’s performance, it is worth noting that ARYANA-BS outperforms all other tools in both tests.\nTo further investigate ARYANA-BS’s performance concerning the sequence with nucleotide insertion or deletion, we simulated\nthree sets of reads with varying indel rates. Specifically, we simulated reads with a low indel rate of 0.001, an indel rate of 0.01,\nand a high indel rate of 0.05. As illustrated in Figure 4, even a minuscule indel rate of 0.001 significantly impacts BSMAP’s\nperformance. Additionally, the results from 0.01 and 0.05 indel rates indicate that ARYANA-BS is more resistant to indel rates\nthan other tools, and it consistently aligns more reads correctly than any other tool.\nPercentage of Reads in CpG Islands and Methylation Percentage\nWe conducted three simulations to investigate the bias of ARYANA-BS toward reads from CpG islands. In the first simulation,\nno reads originated from CpG islands. In the second simulation, 50% of the reads came from CpG islands, while all the reads in\nthe third simulation belonged to CpG islands. Although the results were similar across all simulations, ARYANA-BS consistently\noutperformed the other tools (see Figure 5).\nWe further analyzed the bias of ARYANA-BS and other tools toward methylation percentages of reads. To accomplish this, we\nsimulated reads with varying degrees of methylation, including hypomethylated reads (10% methylation), averagely methylated\nreads (50% methylation), and hypermethylated reads (90% methylation). In all three cases, ARYANA-BS exhibited superior\nperformance compared to other tools. However, no significant differences were observed among all the tools (see Figure 5).\nReal Data Analysis\nTo evaluate the accuracy of the proposed algorithm on real data, we conducted a comparison of the alignment efficiency between\nARYANA-BS and other available tools. The first one million reads from each file of SRR3469520 run from NCBI ( https://trace.\nncbi.nlm.nih.gov/Traces/index.html?view=run_browser&acc=SRR3469520) were used for this purpose.\nAs we lacked knowledge of the exact position of each read in the real data, we computed the alignment penalty of each read\nfor each tool to obtain a fair comparison between the two tools. To ensure a level playing field, we utilized penalty scores from\nbwa-meth. Mismatch penalties were set at 4, gap open penalties were set at 6, gap extension penalties were set at 1, and match\nscores were set at 4. The difference between the alignment penalty of the two tools was then computed for each read.\nFigure 6 showcases the count of reads with differentiations in comparison between ARYANA-BS and other tools, as well as the\nnumber of reads each tool could align while the other failed to do so. It is noteworthy that we did not employ Bismark because\nit was unable to generate output in the case of paired-end reads. It is evident that ARYANA-BS outperformed other tools in this\nanalysis. Although BSMAP demonstrated lower alignment penalty for 4% of reads, it failed to align approximately 29.4% of reads.\nAnalysis of the additional EM-step\nTo investigate the impact of the EM (Expectation-Maximization) step on the improvement of ARYANA-BS results, a dataset\nconsisting of 5 million reads, each with a length of 100 base pairs, was generated from chromosome 21. This was done to achieve\nan approximate sequencing depth of approximately 10X, considering resource constraints that prevented a genome-wide analysis.\nA summary of the ARYANA-BS execution, both without the EM step and with the EM step applied to this dataset, is presented\nin Table 1. In summary, the implementation of the EM step was able to reduce the ARYANA-BS error by 3.23% without any change\nin the needed memory, incurring an additional 9.76% runtime. Furthermore, it increased the percentage of reads aligned to their\ncorrect positions from 90.73% to 91.03%.\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\nARYANA-BS 5\nPercent of correctly mapped reads User+Sys Time (s) Memory (GB)\nARYANA-BS 90.73 3634.33 1.87\nARYANA-BS with EM-step 91.03 3991.57 1.87\nT able 1. Analysis of the additional EM-step on ARYANA-BS\nMethods\nAs mentioned in the background section, the current paradigm in many BS short read aligners is to use a conventional short read\naligner of untreated genomic DNA as a black box (unchanged or with minimal changes) and, rather, adapt the reference genome\nand/or reads (i.e., wild-card, two-letter or three-letter). Information loss, as observed in two- or three-letter methods, as well\nas a biased alignment rate depending on the methylation ratio of the genomic region in wild-card aligners, has been extensively\ndiscussed in the literature as the major limitation of these methods [19].\nContext-aware paradigm\nIn ARYANA-BS we tried to overcome shortcomings of the prior methods by developing a new paradigm that we call context-aware\nalignment. In this paradigm, we try to adapt the seed-and-extend algorithm to better match the BS short read alignment. For\nthis purpose, we need to take well-known biological information about the patterns of DNA methylation in different contexts into\naccount:\n• Dinucleotide context: The distribution of the DNA methylation ratio of cytosines present in CpG dinucleotides is significantly\ndifferent from the other contexts (i.e., CpA, CpC and CpT dinucleotides). Although the presence of 5-methylcytosines in\nDNA was discovered in the 1940s, there was very limited knowledge about non-CpG methylation by the early 2010s [25].\nFollowing major developments in DNA-methylation assays, particularly RRBS and WGBS, more studies have shown the\nexistence of non-CpG methylation in some human tissues (e.g., brain), as well as embryonic stem cells [34]. Further research\nshowed biological functions of non-CpG methylation [26, 17, 28], and suggested epigenetic mechanisms that regulate the\npresence of non-CpG methylation [2, 3]. Some packages perform downstream analysis of DNA methylation data (e.g., finding\ndifferentially methylated regions) by distinguishing between CpG vs. non-CpG methylation [5]. However, the extreme alteration\nof methylation distribution in CpG vs. non-CpG context is considered neither in two/three letters, nor in wild-card alignment.\n• Genomic context: A significant alteration of the methylation pattern was observed in different genomic contexts, particularly\nin active regions (e.g., promoters of expressed genes) [8, 13] vs. silenced regions (e.g., heterochromatin) [30, 33, 29]. These\nalterations have been confirmed at single-cell, cell-type resolution [40]. A common observation has been a significant alteration\nof CpG methylation distribution in CpG islands: although isolated CpGs tend to be hypermethylated in many tissues, those\npresent in CpG-rich regions such as CpG islands, particularly in proximity to active promoters, show lower methylation levels\n[15, 32].\nWe should note that these rules are not zero-one rules, as there are well-known hypermethylated CpG islands in different tissues\nand diseases [16, 39, 37, 6]. There are also observations about flanking regions of CpG islands, called CpG island shores [24]. Altered\nmethylation distribution of isolated CpGs vs. those present in CpG islands can be employed as important prior information that\nwas not taken into account in two/three letter or wild-card alignment.\nARYANA-BS is an enhancement of our conventional short-read aligner ARYANA [11], which performs context-aware alignment\nof BS reads. To better describe ARYANA-BS, we need to have a quick glance over how ARYANA works, and then review what\nenhancements are made to build ARYANA-BS.\nA review of ARYANA\nARYANA uses a seed-and-extend paradigm for aligning short reads of genomic DNA. It creates a Burrows-Wheeler Transform\n(BWT) index of the genome using the BWA engine [22], partitions the reference genome into equal-sized windows, and finds\nmaximal substrings that exactly match between the read and the reference (seeds). For each seed, it scores the genomic windows\nthat contain the seed. It then selects a subset of windows with the maximum scores, finds the precise alignment penalty of the\nread in each window, and reports the alignment position with the minimum penalty. We introduced a bidirectional BWT search\nalgorithm and used it for seed-extension in both directions. The algorithm creates a BWT index on the reference and its reverse\ncomplement, as well as another BWT index on the reverse of the reference and the reference complement. We used the former\nindex to find a minimal seed that did not overlap with the previous seed and used the latter index to extend it. This allowed us to\nmake a significant speedup by creating non overlapping seeds over the read instead of searching every base of the read for a new\nseed. Furthermore, several algorithmic enhancements and techniques are used to improve the efficiency of ARYANA. For example,\nit uses a reset-free hash table as the data structure to search and update window scores. By ”reset-free,” we mean that the hash\ntable does not need to be cleared for each new read. ARYANA is multithreaded and can process both single-end and paired-end\nreads.\nARYANA-BS employs context awareness of DNA methylation patterns in both seed finding and extension phases of read\nalignment, as described below:\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\n6 ARYANA-BS\nContext-aware seed finding\nBy considering alterations in the cytosine-methylation probability distribution across dinucleotide and genomic contexts, ARYANA-\nBS creates five different indexes from the reference genome (figure 7):\n• Index a: the original reference genome, unchanged.\n• Index b: all cytosines that are more likely to be unmethylated, according to their dinucleotide and genomic contexts, are\nconverted to thymines. This resembles the most probable sequence of the genome, after being treated with sodium bisulfite.\nThe default strategy is to consider CpGs outside CpG islands more likely to be methylated, and all other cytosines (e.g., CpAs,\nCpCs, and CpTs across the genome as well as CpGs inside CpG islands) more likely to be unmethylated. The list of genomic\nregions considered to be hypomethylated is provided as an input to the algorithm. By default, it contains CpG islands, but it\ncan be changed depending on the specific organism, tissue or cell type to contain most likely hypomethylated regions across\nthe whole genome.\n• Index c: all cytosines are converted to thymines, regardless of their genomic or dinucleotide contexts. This index is identical to\nthe one used in the three-letter strategy, but as we later show, the extension phase of ARYANA-BS is different from what is\nused in three-letter algorithms.\n• Indexes b’ and c’: similar to genomes b and c, in which, guanine to adenine conversions are made. It is very important to\nnote that PCR amplification of bisulfite-treated DNA fragments can lead to four different sequences from the same region,\ndepending on whether the original forward vs. reverse fragment is used as the PCR template, and whether the final fragment\nbeing sequenced is similar or reverse complement to the template 1. The PCR product contains fragments that are reverse\ncomplemented to the original template from the genomic bisulfite-treated DNA. These fragments contain G to A conversions,\nwhich distinguish them from reverse-strand fragments of the original bisulfite-treated DNA. In genome b’, we select all Gs in\nthe forward strand of the reference genome where the opposite C in the reverse strand is more likely to be unmethylated (as\ndescribed in genome b) and convert them to A. In genome c’, we convert all Gs in the forward strand of the reference genome\nto A.\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\nARYANA-BS 7\nIt is important to note that for each of the five above genomes, we concatenate the sequence and its reverse complement (with\na separator in the middle) and use the resulting sequence to create the BWT index. In this way, both forward and reverse reads\ncan be aligned.\nBy using these five different genomes, we ensure that the context information is used to create longer exact seeds without\ninformation loss. Reads are NOT altered neither in seed finding, nor extension.\nContext-aware seed extension\nAs we mentioned earlier, both ARYANA and ARYANA-BS partition each reference genome into equal-sized windows to find the\nbest part of the genome for read mapping. Each read was aligned independently to each of the five references. For each reference,\nwe find maximal exact matches and score the genomic windows that contain the seed (for more details, see ARYANA article [11]).\nThen, we list the top scored windows and try to extend individual seeds in each window to cover match the whole read.\nThis extension phase is mainly performed by the following steps:\n• A maximal list of consequenced seeds in each window can be determined using a greedy algorithm that guarantees compatibility\nbetween the order of the read and the reference. The seeds in the read are arranged in a nonoverlapping fashion, making the\ngreedy algorithm a viable approach for identifying a maximal list of consequenced seeds that are not overlapped in the reference\nand maintain the same order.\n• Filling the gaps between each pair of consecutive seeds in the list. For this purpose, we have developed a dynamic programming\nalgorithm for finding the optimal-matching between the part of the read between two seeds, and part of the reference located\nbetween the same pair of seeds. Although this algorithm has the same logic as Smith-Waterman, it has several differences. The\nscoring scheme is compliant with bisulfite-sequencing. Therefore, in genomes a, b, and c, we consider zero penalty for genomic\ncytosines that are mapped to read thymines. However, it is important to mention that genomic thymines mapped to read\ncytosines are treated as mismatches, which makes the ARYANA-BS extension different from either two/three-letter or wild-\ncard aligners. Furthermore, we take the dinucleotide context of cytosine into account and treat CpG dinucleotides differently\nfrom CpAs, CpCs and CpTs in terms of the mapping penalty. For genomes b’ and c’, we consider a similar penalty scheme for\ngenomic guanines that are mapped to read adenines.\n• Finally, we sum the total match scores and mismatch/indel penalties for all gaps inside the consecutive seeds. If the data is\npaired end, we look for the best pair of matches, one of read-1 and the other for read-2, which are concordant according to the\ndistancing arguments provided to ARYANA-BS. If no concordant alignment is identified, we can report discordant alignment\nof each read if specified in the arguments.\nEM Algorithm for Improving Methylation Probability Estimation and Read Alignment\nFollowing the initial alignment phase, a subsequent post-processing step is undertaken for the aligned reads against each of the\nfive reference genomes. This process involves the computation of context-aware alignment penalties for the reads within each of\nthese five reference genomes. The alignment with the most favorable penalty score is selected, further enhancing the precision of\nthe alignment. To augment the accuracy of this step, an optional EM algorithm is employed (Figure 8).\nThe EM algorithm plays a pivotal role in estimating the methylation probability of each cytosine, treating it as a latent variable.\nThis methylation probability is then seamlessly integrated into the alignment penalty calculation for each read within each of the\nfive indices. This integration ensures that the resulting alignment not only optimizes the penalty score but also takes into account\nthe methylation probability of each individual cytosine.\nThe algorithm introduces a variable, denoted as θ, which is represented as a tuple θ = (ρ 1, ρ2, ..., ρr). In this representation,\nρi characterizes the alignment of read Ri with one of the five generated indices, and l(ρi) denotes the specific aligned location.\nConsequently, the dataset X encompasses sequences corresponding to each input read.\nFurthermore, a missing variable, Z, is defined as follows:\nZ = (M ethG[C1], M ethG[C2], ..., M ethG[Cψ ])\nIn this definition, G[i] signifies nucleotide i within genome G, and M ethG[Ci] denotes the methylation state (either methylated\nor unmethylated) of each cytosine at the specified genomic locations.\nExpectation phase\nIn the E-step of the EM algorithm, we embark on the task of determining the methylation probability for each cytosine situated\nwithin CpG dinucleotides found in both the forward and reverse strands. This determination is derived from the outcomes of the\nread alignments against the five reference genomes. In this context, each C-to-C alignment (and G-to-G alignment for PCR reads) is\nconsidered representative of a methylated cytosine, while T-to-C and A-to-G alignments are regarded as indicative of unmethylated\ncytosines.\nTo calculate the methylation probability for each cytosine G[Ci] within genome G (where Gi denotes the i-th nucleotide of\ngenome G) based on the estimated parameter ˆθk, the following formula is employed:\nP(M ethG[Ci]|X, ˆθk) = number of C aligned to G[Ci] based on ˆθk\nnumber of C/T aligned to G[Ci] based on ˆθk\nThis formula calculates the likelihood of methylation for a specific cytosine G[Ci] in genome G, taking into account the\ninformation from the read alignments and the parameter estimate ˆθk.\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\n8 ARYANA-BS\nMaximization phase\nIn the maximization step of the EM algorithm, the alignment of reads to each of the five reference indices is carried out based on\nthe methylation probabilities computed in the expectation step. The objective function Q is defined as follows:\nQ(θ|ˆθk) = E[log(P (X, Z|θ))|X, ˆθk]\n=\nZ\nz\nlog(P(X, z|θ))P(z|X, ˆθk)\n=\nZ\nz\nlog(P (X|z, θ)P(z|θ))P(z|X, ˆθk)\n= C +\nZ\nz\nlog(P (X|z, θ))P(z|X, ˆθk)\n= C +\nrX\ni=1\nZ\nz\nlog(P(Ri|z, θ))P(z|X, ˆθk)\n(1)\nAssuming the independence of the alignment probability of Ri[j] to G[l(ρi) + j] from the alignment probability of Ri[j + 1] to\nG[l(ρi) + j + 1], P(Ri|z, θ) can be computed as:\nP(Ri|z, θ) =\nlen(Ri)Y\nj=1\nP(Ri[j]|z, G[l(ρi) + j])\nTherefore we can rewrite the expression 1 as follows:\nQ(θ|ˆθk) = C +\nrX\ni=1\nlen(Ri)X\nj=1\nZ\nz\nlog(P (Ri[j]|z, G[l(ρi) + j]))P(z|X, ˆθk) (2)\nIn a simplified model where ϵ represents the sequencer error probability, P(Ri[k]|z, G[k′]) can be computed as:\nP(Ri[k]|z, G[k′]) =\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n(1 − ϵ) · P(M ethG[k′])+\nϵ/3 · (1 − P(M ethG[k′])) + 2ϵ/3\nG[k′] = C, R[k] = C\n(1 − ϵ) · (1 − P(M ethG[k′]))+\nϵ/3 · P(M ethG[k′]) + 2ϵ/3\nG[k′] = C, Ri[k] = T\nϵ G[k′] = C, Ri[k] = G, A\n1 − ϵ G[k′] ∈ {T, G, A}, Ri[k] = G[k′]\nϵ G [k′] ∈ {T, G, A}, Ri[k] ̸= G[k′]\nAssuming a mismatch penalty equal to − log(ϵ), log(P(Ri[k]|z, G[k′])) can be approximated as:\nlog(P(Ri[k]|z, G[k′])) ≃\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nlog(P(M ethG[k′])) G[k′] = C, Ri[k] = C\nlog(1 − P(M ethG[k′])) G[k′] = C, Ri[k] = T\nmismatch penalty G[k′] = C, Ri[k] = G, A\n0 G[k′] ∈ {T, G, A}, Ri[k] = G[k′]\nmismatch penalty G[k′] ∈ {T, G, A}, Ri[k] ̸= G[k′]\nIn line with the provided explanations, to determine θ for maximizing Q(θ|ˆθk), the values of ρi need to be determined in a\nmanner that maximizes the expression 2. Given that the values of ρi are independent of each other, and the effect of each one on\nexpression 2 is independent of the others, for each read Ri, the value of ρi is set in a way that maximizes the following:\nlen(Ri)X\nj=1\nZ\nz\nlog(P (Ri[j]|z, G[l(ρi) + j]))P(z|X, ˆθk) (3)\nDiscussion\nWe have improved the ARYANA aligner as the ARYANA-BS aligner to align WGBS reads. ARYANA-BS uses the theoretical\nknowledge about the methylation ratio of each position of the genome to have a better alignment.\nWe have compared ARYANA-BS with BSMAP, bwa-meth, Bismark, BSBolt, and abismal to assess the proposed algorithm.\nThe comparison has shown that the ARYANA-BS aligner improves previous works in the amount of correctly mapped reads for\nsimulated reads and reduces penalties and increases mapped reads in the alignment of real reads. Additionally, ARYANA-BS has\na comparable memory footprint and runtime to other tools.\nARYANA-BS is more resistant to biases in the genomic context, such as hypermethylation, hypomethylation, indels and SNP\ncounts. This makes it the best choice for analyses that are based on genomic changes, such as cancer analysis and cell-free DNA\nanalysis.\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\nARYANA-BS 9\nAcknowledgments\nThe authors are grateful to Maryam Rabiee who made great contributions to the initial development of ARYANA-BS. We thank\nRichard Dannebaum for his support in this work.\nReferences\n1. Sherman, a simple bisulfite fastq read simulator (biqrs).\n2. Julia Arand, David Spieler, Tommy Karius, Miguel R Branco, Daniela Meilinger, Alexander Meissner, Thomas Jenuwein,\nGuoliang Xu, Heinrich Leonhardt, Verena Wolf, et al. In vivo control of cpg and non-cpg dna methylation by dna\nmethyltransferases. PLoS genetics, 8(6):e1002750, 2012.\n3. Dheepa Balasubramanian, Batool Akhtar-Zaidi, Lingyun Song, Cynthia F Bartels, Martina Veigl, Lydia Beard, Lois Myeroff,\nKishore Guda, James Lutterbaugh, Joseph Willis, et al. H3k4me3 inversely correlates with dna methylation at a large class of\nnon-cpg-island-containing start sites. Genome medicine, 4:1–11, 2012.\n4. Christoph Bock. Analysing and interpreting dna methylation data. Nature Reviews Genetics, 13(10):705–719, 2012.\n5. Marco Catoni, Jonathan MF Tsang, Alessandro P Greco, and Nicolae Radu Zabet. Dmrcaller: a versatile r/bioconductor\npackage for detection and visualization of differentially methylated regions in cpg and non-cpg contexts.Nucleic acids research,\n46(19):e114–e114, 2018.\n6. Guilherme da Silva Rodrigues, Nat´ alia Y Noronha, Mariana L de Almeida, Andressa C da S Sobrinho, Ligia M Watanabe,\nMarcela A de S Pinhel, Jo˜ ao GR de Lima, Ren Zhang, Carla B Nonino, Christiano RR Alves, et al. Exercise training modifies\nthe whole-blood methylation profile in middle-aged and older women. Journal of Applied Physiology, 2023.\n7. Guilherme de Sena Brandine and Andrew D Smith. Fast and memory-efficient mapping of short bisulfite sequencing reads\nusing a two-letter alphabet. NAR Genomics and Bioinformatics, 3(4):lqab115, 2021.\n8. Melanie Ehrlich and Michelle Lacey. Dna methylation and differentiation: silencing, upregulation and modulation of gene\nexpression. Epigenomics, 5(5):553–568, 2013.\n9. Colin Farrell, Michael Thompson, Anela Tosevska, Adewale Oyetunde, and Matteo Pellegrini. Bisulfite bolt: A bisulfite\nsequencing analysis platform. Gigascience, 10(5):giab033, 2021.\n10. Suhua Feng, Liudmilla Rubbi, Steven E Jacobsen, and Matteo Pellegrini. Determining dna methylation profiles using\nsequencing. In High-Throughput Next Generation Sequencing, pages 223–238. Springer, 2011.\n11. Milad Gholami, Aryan Arbabi, Ali Sharifi-Zarchi, Hamidreza Chitsaz, and Mehdi Sadeghi. Aryana: Aligning reads by yet\nanother approach. In BMC bioinformatics, volume 15, pages 1–10. BioMed Central, 2014.\n12. Wentao Gong, Xiangchun Pan, Dantong Xu, Guanyu Ji, Yifei Wang, Yuhan Tian, Jiali Cai, Jiaqi Li, Zhe Zhang, and Xiaolong\nYuan. Benchmarking dna methylation analysis of 14 alignment algorithms for whole genome bisulfite sequencing in mammals.\nComputational and structural biotechnology journal , 20:4704–4716, 2022.\n13. Maxim VC Greenberg and Deborah Bourc’his. The diverse roles of dna methylation in mammalian development and disease.\nNature reviews Molecular cell biology , 20(10):590–607, 2019.\n14. Hikoya Hayatsu. Discovery of bisulfite-mediated cytosine conversion to uracil, the key reaction for dna methylation analysis—a\npersonal account. Proceedings of the Japan Academy, Series B, 84(8):321–330, 2008.\n15. Amber Hogart, Jens Lichtenberg, Subramanian S Ajay, Stacie Anderson, Elliott H Margulies, David M Bodine, NIH\nIntramural Sequencing Center, et al. Genome-wide dna methylation profiles in hematopoietic stem and progenitor cells reveal\noverrepresentation of ets transcription factor binding sites. Genome research, 22(8):1407–1418, 2012.\n16. Tim Hui-Ming Huang, Martin R Perry, and Douglas E Laux. Methylation profiling of cpg islands in human breast cancer cells.\nHuman molecular genetics , 8(3):459–470, 1999.\n17. Hyun Sik Jang, Woo Jung Shin, Jeong Eon Lee, and Jeong Tae Do. Cpg and non-cpg methylation in epigenetic gene regulation\nand brain function. Genes, 8(6):148, 2017.\n18. Felix Krueger and Simon R Andrews. Bismark: a flexible aligner and methylation caller for bisulfite-seq applications.\nbioinformatics, 27(11):1571–1572, 2011.\n19. Govindarajan Kunde-Ramamoorthy, Cristian Coarfa, Eleonora Laritsky, Noah J Kessler, R Alan Harris, Mingchu Xu, Rui\nChen, Lanlan Shen, Aleksandar Milosavljevic, and Robert A Waterland. Comparison and quantitative verification of mapping\nalgorithms for whole-genome bisulfite sequencing. Nucleic acids research, 42(6):e43–e43, 2014.\n20. Sergey Kurdyukov and Martyn Bullock. Dna methylation analysis: choosing the right method. Biology, 5(1):3, 2016.\n21. Ben Langmead and Steven L Salzberg. Fast gapped-read alignment with bowtie 2. Nature methods, 9(4):357–359, 2012.\n22. Heng Li and Richard Durbin. Fast and accurate short read alignment with burrows–wheeler transform. bioinformatics,\n25(14):1754–1760, 2009.\n23. Alexander Meissner, Andreas Gnirke, George W Bell, Bernard Ramsahoye, Eric S Lander, and Rudolf Jaenisch. Reduced\nrepresentation bisulfite sequencing for comparative high-resolution dna methylation analysis. Nucleic acids research ,\n33(18):5868–5877, 2005.\n24. Risa Mitsumori, Kazuya Sakaguchi, Daichi Shigemizu, Taiki Mori, Shintaro Akiyama, Kouichi Ozaki, Shumpei Niida, and\nNobuyoshi Shimoda. Lower dna methylation levels in cpg island shores of cr1, clu, and picalm in the blood of japanese\nalzheimer’s disease patients. PLoS One, 15(9):e0239196, 2020.\n25. Lisa D Moore, Thuc Le, and Guoping Fan. Dna methylation and its basic function. Neuropsychopharmacology, 38(1):23–38,\n2013.\n26. Vibha Patil, Robyn L Ward, and Luke B Hesson. The evidence for functional non-cpg methylation in mammalian cells.\nEpigenetics, 9(6):823–828, 2014.\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\n10 ARYANA-BS\n27. Brent S. Pedersen, Kenneth Eyring, Subhajyoti De, Ivana V. Yang, and David A. Schwartz. Fast and accurate alignment of\nlong bisulfite-seq reads, 2014.\n28. Deepa Ramasamy, Arunagiri Kuha Deva Magendhra Rao, Thangarajan Rajkumar, and Samson Mani. Non-cpg methylation—a\nkey epigenetic modification in cancer. Briefings in Functional Genomics , 20(5):304–311, 2021.\n29. Wendan Ren, Huitao Fan, Sara A Grimm, Jae Jin Kim, Linhui Li, Yiran Guo, Christopher James Petell, Xiao-Feng Tan,\nZhi-Min Zhang, John P Coan, et al. Dnmt1 reads heterochromatic h4k20me3 to reinforce line-1 dna methylation. Nature\ncommunications, 12(1):2490, 2021.\n30. MR Rountree and EU Selker. Dna methylation and the formation of heterochromatin in neurospora crassa.Heredity, 105(1):38–\n44, 2010.\n31. Sophie Schbath, V´ eronique Martin, Matthias Zytnicki, Julien Fayolle, Valentin Loux, and Jean-Fran¸ cois Gibrat. Mapping reads\non a genomic sequence: an algorithmic overview and a practical comparative analysis. Journal of Computational Biology ,\n19(6):796–813, 2012.\n32. Yonghwan Shin, Minkyoung Kim, Jonghwa Won, Junchul Kim, Seog Bae Oh, Jong-Ho Lee, and Kyungpyo Park. Epigenetic\nmodification of cftr in head and neck cancer. Journal of clinical medicine, 9(3):734, 2020.\n33. Feng Tan, Yue Lu, Wei Jiang, Tian Wu, Ruoyu Zhang, Yu Zhao, and Dao-Xiu Zhou. Ddm1 represses noncoding rna expression\nand rna-directed dna methylation in heterochromatin. Plant physiology, 177(3):1187–1197, 2018.\n34. Katherine E Varley, Jason Gertz, Kevin M Bowling, Stephanie L Parker, Timothy E Reddy, Florencia Pauli-Behn, Marie K\nCross, Brian A Williams, John A Stamatoyannopoulos, Gregory E Crawford, et al. Dynamic dna methylation across diverse\nhuman cell lines and tissues. Genome research, 23(3):555–567, 2013.\n35. Annalisa Varriale. Dna methylation, epigenetics, and evolution in vertebrates: facts and challenges. International journal of\nevolutionary biology, 2014, 2014.\n36. Michael Weber, Jonathan J Davies, David Wittig, Edward J Oakeley, Michael Haase, Wan L Lam, and Dirk Schuebeler.\nChromosome-wide and promoter-specific analyses identify sites of differential dna methylation in normal and transformed\nhuman cells. Nature genetics, 37(8):853–862, 2005.\n37. Lu Wen, Jingyi Li, Huahu Guo, Xiaomeng Liu, Shengmin Zheng, Dafang Zhang, Weihua Zhu, Jianhui Qu, Limin Guo, Dexiao\nDu, et al. Genome-scale detection of hypermethylated cpg islands in circulating cell-free dna of hepatocellular carcinoma\npatients. Cell research, 25(11):1250–1264, 2015.\n38. Yuanxin Xi and Wei Li. Bsmap: whole genome bisulfite sequence mapping program. BMC bioinformatics, 10(1):1–9, 2009.\n39. Srinivasan Yegnasubramanian, Jeanne Kowalski, Mark L Gonzalgo, Marianna Zahurak, Steven Piantadosi, Patrick C Walsh,\nG Steven Bova, Angelo M De Marzo, William B Isaacs, and William G Nelson. Hypermethylation of cpg islands in primary\nand metastatic human prostate cancer. Cancer research, 64(6):1975–1986, 2004.\n40. Tianyu Zhu, Jacklyn Liu, Stephan Beck, Sun Pan, David Capper, Matt Lechner, Chrissie Thirlwell, Charles E Breeze, and\nAndrew E Teschendorff. A pan-tissue dna methylation atlas enables in silico decomposition of human tissue methylomes at\ncell-type resolution. Nature Methods, 19(3):296–306, 2022.\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\nARYANA-BS 11\n/uni00000013\n/uni00000015/uni00000013\n/uni00000017/uni00000013\n/uni00000019/uni00000013\n/uni0000001b/uni00000013\n/uni00000014/uni00000013/uni00000013/uni00000033/uni00000048/uni00000055/uni00000046/uni00000048/uni00000051/uni00000057/uni00000003/uni00000052/uni00000049/uni00000003/uni00000046/uni00000052/uni00000055/uni00000055/uni00000048/uni00000046/uni00000057/uni0000004f/uni0000005c/uni00000003/uni00000050/uni00000044/uni00000053/uni00000053/uni00000048/uni00000047/uni00000003/uni00000055/uni00000048/uni00000044/uni00000047/uni00000056\n/uni0000001c/uni00000014/uni00000011/uni00000018/uni00000019\n/uni0000001c/uni00000017/uni00000011/uni0000001a/uni0000001a\n/uni0000001c/uni00000015/uni00000011/uni00000013/uni0000001b\n/uni0000001c/uni00000018/uni00000011/uni00000015/uni0000001c\n/uni0000001c/uni00000013/uni00000011/uni00000014/uni00000013/uni0000001b/uni0000001b/uni00000011/uni00000019/uni00000013\n/uni00000031/uni00000044/uni00000031\n/uni0000001b/uni0000001b/uni00000011/uni00000019/uni0000001a\n/uni00000031/uni00000044/uni00000031\n/uni0000001b/uni0000001b/uni00000011/uni00000016/uni00000019\n/uni00000018/uni00000018/uni00000011/uni00000014/uni00000017\n/uni0000001a/uni00000013/uni00000011/uni0000001b/uni0000001a\n/uni00000018/uni00000018/uni00000011/uni00000014/uni0000001c\n/uni0000001a/uni00000013/uni00000011/uni0000001b/uni00000017\n/uni00000018/uni00000017/uni00000011/uni00000019/uni00000013\n/uni00000017/uni00000017/uni00000011/uni00000014/uni00000013/uni00000017/uni00000018/uni00000011/uni00000018/uni00000016\n/uni00000031/uni00000044/uni00000031 /uni00000031/uni00000044/uni00000031\n/uni00000017/uni00000017/uni00000011/uni00000015/uni00000019\n/uni00000018/uni00000014/uni00000011/uni0000001b/uni00000013\n/uni00000019/uni00000016/uni00000011/uni00000015/uni00000018\n/uni00000018/uni00000014/uni00000011/uni0000001c/uni00000013\n/uni00000019/uni00000017/uni00000011/uni00000016/uni00000017\n/uni00000018/uni00000014/uni00000011/uni00000016/uni00000019\n/uni00000017/uni0000001a/uni00000011/uni0000001b/uni00000019/uni00000017/uni00000019/uni00000011/uni00000019/uni00000017\n/uni00000017/uni00000017/uni00000011/uni00000018/uni00000018/uni00000017/uni00000019/uni00000011/uni00000013/uni00000017/uni00000017/uni0000001a/uni00000011/uni00000015/uni0000001c\n/uni00000024/uni00000035/uni0000003c/uni00000024/uni00000031/uni00000024/uni00000010/uni00000025/uni00000036\n/uni00000025/uni00000036/uni00000030/uni00000024/uni00000033\n/uni00000045/uni0000005a/uni00000044/uni00000010/uni00000050/uni00000048/uni00000057/uni0000004b/uni00000025/uni0000004c/uni00000056/uni00000050/uni00000044/uni00000055/uni0000004e/uni00000025/uni00000036/uni00000025/uni00000052/uni0000004f/uni00000057/uni00000044/uni00000045/uni0000004c/uni00000056/uni00000050/uni00000044/uni0000004f\n/uni00000013/uni00000011/uni00000013\n/uni00000013/uni00000011/uni00000014\n/uni00000013/uni00000011/uni00000015\n/uni00000013/uni00000011/uni00000016\n/uni00000013/uni00000011/uni00000017\n/uni00000013/uni00000011/uni00000018/uni00000029/uni00000027/uni00000035/uni00000003/uni00000055/uni00000044/uni00000057/uni00000048\n/uni00000013/uni00000011/uni00000013/uni0000001b\n/uni00000013/uni00000011/uni00000013/uni00000018\n/uni00000013/uni00000011/uni00000013/uni0000001b\n/uni00000013/uni00000011/uni00000013/uni00000018\n/uni00000013/uni00000011/uni00000014/uni00000013\n/uni00000013/uni00000011/uni00000013/uni00000013 /uni00000031/uni00000044/uni00000031 /uni00000013/uni00000011/uni00000013/uni00000013 /uni00000031/uni00000044/uni00000031 /uni00000013/uni00000011/uni00000013/uni00000013\n/uni00000013/uni00000011/uni00000015/uni00000017\n/uni00000013/uni00000011/uni00000015/uni00000015\n/uni00000013/uni00000011/uni00000015/uni00000016\n/uni00000013/uni00000011/uni00000015/uni00000015\n/uni00000013/uni00000011/uni00000015/uni00000018\n/uni00000013/uni00000011/uni00000013/uni00000013 /uni00000013/uni00000011/uni00000013/uni00000013 /uni00000031/uni00000044/uni00000031 /uni00000031/uni00000044/uni00000031 /uni00000013/uni00000011/uni00000013/uni00000013\n/uni00000013/uni00000011/uni00000017/uni00000013\n/uni00000013/uni00000011/uni00000016/uni00000018\n/uni00000013/uni00000011/uni00000017/uni00000017\n/uni00000013/uni00000011/uni00000016/uni00000018\n/uni00000013/uni00000011/uni00000017/uni00000013\n/uni00000013/uni00000011/uni00000013/uni00000018\n/uni00000013/uni00000011/uni00000013/uni00000014 /uni00000013/uni00000011/uni00000013/uni00000014\n/uni00000013/uni00000011/uni00000013/uni00000013\n/uni00000013/uni00000011/uni00000013/uni00000018\n/uni00000013\n/uni00000018/uni00000013/uni00000013/uni00000013\n/uni00000014/uni00000013/uni00000013/uni00000013/uni00000013\n/uni00000014/uni00000018/uni00000013/uni00000013/uni00000013\n/uni00000015/uni00000013/uni00000013/uni00000013/uni00000013/uni00000038/uni00000056/uni00000048/uni00000055/uni0000000e/uni00000036/uni0000005c/uni00000056/uni00000003/uni00000037/uni0000004c/uni00000050/uni00000048/uni00000003/uni0000000b/uni00000056/uni0000000c\n/uni00000015/uni00000014/uni00000014/uni00000018/uni00000011/uni00000014/uni00000017\n/uni00000017/uni0000001c/uni00000015/uni00000018/uni00000011/uni00000016/uni00000018/uni00000017/uni0000001a/uni00000018/uni0000001c/uni00000011/uni0000001c/uni0000001a\n/uni00000014/uni00000016/uni00000014/uni00000015/uni00000016/uni00000011/uni00000016/uni00000019\n/uni00000015/uni00000019/uni0000001c/uni00000014/uni00000011/uni00000014/uni00000015\n/uni00000014/uni0000001b/uni0000001a/uni00000011/uni0000001b/uni00000013/uni00000031/uni00000044/uni00000031\n/uni0000001b/uni00000013/uni00000019/uni00000017/uni00000011/uni00000013/uni0000001c\n/uni00000031/uni00000044/uni00000031 /uni00000016/uni00000016/uni0000001c/uni00000011/uni00000018/uni00000015\n/uni00000014/uni00000019/uni00000016/uni00000016/uni00000011/uni0000001a/uni0000001b\n/uni0000001a/uni00000016/uni00000017/uni00000016/uni00000011/uni0000001a/uni00000016\n/uni00000016/uni0000001a/uni00000014/uni00000017/uni00000011/uni00000015/uni00000019\n/uni00000014/uni0000001c/uni00000014/uni0000001a/uni00000017/uni00000011/uni00000016/uni00000015\n/uni00000015/uni00000014/uni0000001b/uni00000018/uni00000011/uni0000001b/uni0000001b\n/uni00000016/uni00000019/uni00000018/uni00000019/uni00000011/uni00000018/uni00000016\n/uni0000001b/uni00000019/uni00000016/uni00000013/uni00000011/uni00000014/uni0000001b\n/uni00000031/uni00000044/uni00000031 /uni00000031/uni00000044/uni00000031\n/uni00000017/uni00000014/uni00000018/uni00000013/uni00000011/uni00000013/uni0000001c\n/uni00000014/uni00000017/uni00000014/uni00000015/uni00000011/uni00000019/uni00000016\n/uni00000018/uni00000018/uni0000001b/uni0000001a/uni00000011/uni00000019/uni0000001c\n/uni00000018/uni00000013/uni00000018/uni0000001b/uni00000011/uni00000013/uni0000001b\n/uni00000014/uni00000019/uni00000019/uni00000013/uni00000016/uni00000011/uni00000018/uni00000015\n/uni00000014/uni00000019/uni00000018/uni0000001b/uni00000011/uni00000016/uni00000014\n/uni00000014/uni0000001c/uni0000001a/uni00000011/uni0000001b/uni00000015\n/uni0000001c/uni0000001a/uni00000016/uni00000011/uni00000015/uni00000017/uni00000019/uni0000001b/uni00000018/uni00000011/uni00000019/uni00000015\n/uni00000016/uni00000013/uni00000018/uni00000015/uni00000011/uni00000017/uni00000016\n/uni00000014/uni0000001c/uni00000017/uni00000011/uni00000018/uni00000014\n/uni00000036/uni00000028/uni00000003/uni00000014/uni00000013/uni00000013/uni00000045/uni00000053/uni00000036/uni00000028/uni00000003/uni00000016/uni00000013/uni00000013/uni00000045/uni00000053/uni00000033/uni00000028/uni00000003/uni00000014/uni00000013/uni00000013/uni00000045/uni00000053/uni00000033/uni00000028/uni00000003/uni00000016/uni00000013/uni00000013/uni00000045/uni00000053/uni00000036/uni00000028/uni00000003/uni00000014/uni00000013/uni00000013/uni00000045/uni00000053\n/uni0000005a/uni0000004c/uni00000057/uni0000004b/uni00000003/uni00000036/uni0000004b/uni00000048/uni00000055/uni00000050/uni00000044/uni00000051\n/uni00000013\n/uni00000015\n/uni00000017\n/uni00000019\n/uni0000001b\n/uni00000014/uni00000013\n/uni00000014/uni00000015\n/uni00000014/uni00000017/uni00000030/uni00000048/uni00000050/uni00000052/uni00000055/uni0000005c/uni00000003/uni0000000b/uni0000002a/uni00000025/uni0000000c\n/uni0000001b/uni00000011/uni00000018/uni00000017 /uni0000001b/uni00000011/uni00000018/uni00000017 /uni0000001b/uni00000011/uni00000018/uni00000017 /uni0000001b/uni00000011/uni00000018/uni00000017 /uni0000001b/uni00000011/uni00000018/uni00000017\n/uni0000001b/uni00000011/uni00000014/uni0000001c\n/uni00000031/uni00000044/uni00000031\n/uni0000001b/uni00000011/uni00000015/uni00000018\n/uni00000031/uni00000044/uni00000031\n/uni0000001b/uni00000011/uni00000014/uni0000001c\n/uni00000014/uni00000014/uni00000011/uni00000018/uni0000001a/uni00000014/uni00000014/uni00000011/uni00000017/uni0000001a/uni00000014/uni00000014/uni00000011/uni00000018/uni0000001b/uni00000014/uni00000014/uni00000011/uni00000019/uni00000013/uni00000014/uni00000014/uni00000011/uni00000019/uni00000015\n/uni00000016/uni00000011/uni00000016/uni00000018 /uni00000016/uni00000011/uni00000016/uni00000018\n/uni00000031/uni00000044/uni00000031 /uni00000031/uni00000044/uni00000031\n/uni00000016/uni00000011/uni00000016/uni00000018\n/uni00000014/uni00000016/uni00000011/uni00000013/uni0000001a/uni00000014/uni00000016/uni00000011/uni00000014/uni00000013/uni00000014/uni00000016/uni00000011/uni00000013/uni00000015/uni00000014/uni00000016/uni00000011/uni00000013/uni0000001c/uni00000014/uni00000016/uni00000011/uni00000014/uni00000015\n/uni00000015/uni00000011/uni0000001a/uni00000014 /uni00000015/uni00000011/uni0000001a/uni00000014 /uni00000015/uni00000011/uni0000001a/uni00000014 /uni00000015/uni00000011/uni0000001a/uni00000014 /uni00000015/uni00000011/uni0000001a/uni00000014\nFig. 2. Comparison of ARYANA, BSMAP, bwa-meth, Bismark, BSBolt, abismal . We have shown four comparisons: percent of correctly\nmapped reads, FDR (false discovery rate), memory footprint, and runtime. We compared these tools with five simulated inputs: 100 base pairs single-\nend reads, 300 base pairs single-end reads, 100 base pairs paired-end reads, 300 base pairs paired-end reads, all simulated with ARYANA read simulator,\nand 100 base pairs single-end reads simulated with Sherman.\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\n12 ARYANA-BS\n/uni00000036/uni00000028/uni00000003/uni00000014/uni00000013/uni00000013/uni00000045/uni00000053\n/uni00000014/uni00000013/uni00000011/uni00000019/uni00000008\n/uni00000017/uni00000014/uni00000011/uni00000015/uni00000008\n/uni00000013/uni00000011/uni00000018/uni00000008\n/uni00000017/uni0000001a/uni00000011/uni00000016/uni00000008\n/uni00000013/uni00000011/uni00000017/uni00000008\n/uni00000036/uni00000028/uni00000003/uni00000016/uni00000013/uni00000013/uni00000045/uni00000053\n/uni00000014/uni00000019/uni00000011/uni00000016/uni00000008\n/uni00000016/uni00000017/uni00000011/uni00000019/uni00000008\n/uni00000013/uni00000011/uni00000015/uni00000008\n/uni00000017/uni0000001b/uni00000011/uni0000001b/uni00000008\n/uni00000013/uni00000011/uni00000015/uni00000008\n/uni00000033/uni00000028/uni00000003/uni00000014/uni00000013/uni00000013/uni00000045/uni00000053\n/uni00000014/uni00000014/uni00000011/uni00000018/uni00000008\n/uni00000016/uni0000001c/uni00000011/uni0000001b/uni00000008\n/uni00000013/uni00000011/uni0000001a/uni00000008\n/uni00000017/uni0000001a/uni00000011/uni00000016/uni00000008\n/uni00000013/uni00000011/uni00000019/uni00000008\n/uni00000032/uni00000055/uni0000004c/uni0000004a/uni0000004c/uni00000051/uni00000044/uni0000004f/uni00000003/uni0000004c/uni00000051/uni00000047/uni00000048/uni0000005b\n/uni0000002f/uni0000004c/uni0000004e/uni00000048/uni0000004f/uni0000005c/uni00000003/uni00000057/uni00000052/uni00000003/uni00000045/uni00000048/uni00000003/uni00000058/uni00000051/uni00000050/uni00000048/uni00000057/uni0000004b/uni0000005c/uni0000004f/uni00000044/uni00000057/uni00000048/uni00000047/uni0000000f/uni00000003/uni00000026/uni00000003/uni00000057/uni00000052/uni00000003/uni00000037\n/uni00000024/uni0000004f/uni0000004f/uni00000003/uni00000026/uni00000003/uni00000057/uni00000052/uni00000003/uni00000037\n/uni0000002f/uni0000004c/uni0000004e/uni00000048/uni0000004f/uni0000005c/uni00000003/uni00000057/uni00000052/uni00000003/uni00000045/uni00000048/uni00000003/uni00000058/uni00000051/uni00000050/uni00000048/uni00000057/uni0000004b/uni0000005c/uni0000004f/uni00000044/uni00000057/uni00000048/uni00000047/uni0000000f/uni00000003/uni0000002a/uni00000003/uni00000057/uni00000052/uni00000003/uni00000024\n/uni00000024/uni0000004f/uni0000004f/uni00000003/uni0000002a/uni00000003/uni00000057/uni00000052/uni00000003/uni00000024\n/uni00000033/uni00000028/uni00000003/uni00000016/uni00000013/uni00000013/uni00000045/uni00000053\n/uni00000014/uni00000019/uni00000011/uni00000014/uni00000008\n/uni00000016/uni00000017/uni00000011/uni00000019/uni00000008\n/uni00000013/uni00000011/uni00000016/uni00000008\n/uni00000017/uni0000001b/uni00000011/uni0000001b/uni00000008\n/uni00000013/uni00000011/uni00000015/uni00000008\n/uni00000036/uni00000028/uni00000003/uni00000014/uni00000013/uni00000013/uni00000045/uni00000053\n/uni0000005a/uni0000004c/uni00000057/uni0000004b/uni00000003/uni00000036/uni0000004b/uni00000048/uni00000055/uni00000050/uni00000044/uni00000051\n/uni0000001c/uni00000011/uni00000017/uni00000008\n/uni00000017/uni00000013/uni00000011/uni0000001a/uni00000008\n/uni00000015/uni00000011/uni00000017/uni00000008\n/uni00000017/uni00000018/uni00000011/uni00000016/uni00000008\n/uni00000015/uni00000011/uni00000014/uni00000008\nFig. 3. Percent of alignment of reads to each index . This figure shows the percentage of each dataset that aligned to each index. The majority of\nthe reads aligned to the context-aware indexes, rather than the original index and three-letter indexes.\n/uni00000017/uni00000003/uni00000050/uni0000004c/uni0000004f/uni0000004c/uni00000052/uni00000051/uni00000017/uni00000013/uni00000003/uni00000050/uni0000004c/uni0000004f/uni0000004c/uni00000052/uni00000051\n/uni00000036/uni00000031/uni00000033/uni00000003/uni00000026/uni00000052/uni00000058/uni00000051/uni00000057\n/uni00000013\n/uni00000015/uni00000013\n/uni00000017/uni00000013\n/uni00000019/uni00000013\n/uni0000001b/uni00000013\n/uni00000014/uni00000013/uni00000013/uni00000033/uni00000048/uni00000055/uni00000046/uni00000048/uni00000051/uni00000057/uni00000003/uni00000052/uni00000049/uni00000003/uni00000046/uni00000052/uni00000055/uni00000055/uni00000048/uni00000046/uni00000057/uni0000004f/uni0000005c/uni00000003/uni00000050/uni00000044/uni00000053/uni00000053/uni00000048/uni00000047/uni00000003/uni00000055/uni00000048/uni00000044/uni00000047/uni00000056\n/uni0000001c/uni00000016/uni00000011/uni00000015/uni00000017/uni0000001c/uni00000017/uni00000011/uni00000016/uni00000013\n/uni0000001c/uni00000014/uni00000011/uni0000001a/uni00000016/uni0000001c/uni00000014/uni00000011/uni00000018/uni00000019\n/uni00000018/uni0000001a/uni00000011/uni00000017/uni0000001b/uni00000018/uni00000019/uni00000011/uni00000013/uni00000018\n/uni00000017/uni00000018/uni00000011/uni0000001a/uni00000017\n/uni00000017/uni00000015/uni00000011/uni00000016/uni0000001a\n/uni00000018/uni00000018/uni00000011/uni00000015/uni00000017/uni00000018/uni00000017/uni00000011/uni00000013/uni0000001a\n/uni00000018/uni00000013/uni00000011/uni0000001a/uni0000001c/uni00000017/uni0000001c/uni00000011/uni00000016/uni0000001a\n/uni00000013/uni00000011/uni00000013/uni00000013/uni00000014/uni00000013/uni00000011/uni00000013/uni00000014/uni00000013/uni00000011/uni00000013/uni00000018\n/uni0000002c/uni00000051/uni00000047/uni00000048/uni0000004f/uni00000003/uni00000035/uni00000044/uni00000057/uni00000048\n/uni0000001c/uni00000017/uni00000011/uni00000018/uni00000019/uni0000001c/uni00000017/uni00000011/uni00000014/uni0000001c\n/uni00000019/uni0000001a/uni00000011/uni00000016/uni00000018\n/uni0000001a/uni0000001c/uni00000011/uni0000001c/uni00000015\n/uni00000015/uni00000018/uni00000011/uni00000019/uni00000014\n/uni00000013/uni00000011/uni00000015/uni00000017\n/uni00000018/uni0000001a/uni00000011/uni00000015/uni0000001a\n/uni00000018/uni00000017/uni00000011/uni00000013/uni00000018\n/uni00000016/uni00000018/uni00000011/uni0000001c/uni00000015\n/uni00000017/uni00000016/uni00000011/uni0000001b/uni00000015\n/uni00000015/uni00000017/uni00000011/uni0000001b/uni0000001c\n/uni00000013/uni00000011/uni00000014/uni00000019\n/uni00000018/uni00000018/uni00000011/uni00000013/uni0000001c\n/uni00000018/uni00000015/uni00000011/uni00000015/uni0000001c\n/uni00000016/uni00000019/uni00000011/uni0000001c/uni00000014\n/uni00000018/uni00000013/uni00000011/uni00000016/uni0000001b\n/uni00000017/uni00000017/uni00000011/uni0000001c/uni00000017\n/uni00000014/uni00000015/uni00000011/uni00000014/uni0000001a\n/uni00000024/uni00000035/uni0000003c/uni00000024/uni00000031/uni00000024/uni00000010/uni00000025/uni00000036\n/uni00000025/uni00000036/uni00000030/uni00000024/uni00000033\n/uni00000045/uni0000005a/uni00000044/uni00000010/uni00000050/uni00000048/uni00000057/uni0000004b\n/uni00000025/uni0000004c/uni00000056/uni00000050/uni00000044/uni00000055/uni0000004e\n/uni00000025/uni00000036/uni00000025/uni00000052/uni0000004f/uni00000057/uni00000044/uni00000045/uni0000004c/uni00000056/uni00000050/uni00000044/uni0000004f\nFig. 4. Scrutinize of tools against different SNP counts and indel rates We generated two different simulated reads with different SNP counts.\nThis figure shows the percentage of correctly mapped reads for each tool case. In both cases, ARYANA-BS performed better than the other tools.\nAdditionally, we generated three different simulated reads with different indel rates, and again ARYANA-BS mapped more reads correctly with different\nindel rates than others.\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\nARYANA-BS 13\n/uni00000013/uni00000008/uni00000018/uni00000013/uni00000008/uni00000014/uni00000013/uni00000013/uni00000008\n/uni00000033/uni00000048/uni00000055/uni00000046/uni00000048/uni00000051/uni00000057/uni00000003/uni00000052/uni00000049/uni00000003/uni00000055/uni00000048/uni00000044/uni00000047/uni00000056/uni00000003/uni0000004c/uni00000051/uni00000003/uni00000026/uni00000033/uni0000002a/uni00000003/uni0000004c/uni00000056/uni0000004f/uni00000044/uni00000051/uni00000047\n/uni00000013\n/uni00000015/uni00000013\n/uni00000017/uni00000013\n/uni00000019/uni00000013\n/uni0000001b/uni00000013\n/uni00000014/uni00000013/uni00000013/uni00000033/uni00000048/uni00000055/uni00000046/uni00000048/uni00000051/uni00000057/uni00000003/uni00000052/uni00000049/uni00000003/uni00000046/uni00000052/uni00000055/uni00000055/uni00000048/uni00000046/uni00000057/uni0000004f/uni0000005c/uni00000003/uni00000050/uni00000044/uni00000053/uni00000053/uni00000048/uni00000047/uni00000003/uni00000055/uni00000048/uni00000044/uni00000047/uni00000056\n/uni0000001c/uni00000016/uni00000011/uni00000015/uni00000017\n/uni0000001c/uni00000013/uni00000011/uni0000001c/uni00000013\n/uni0000001b/uni0000001a/uni00000011/uni00000019/uni00000016\n/uni0000001c/uni00000014/uni00000011/uni0000001a/uni00000016\n/uni0000001b/uni0000001a/uni00000011/uni00000013/uni0000001b\n/uni0000001b/uni00000015/uni00000011/uni00000019/uni00000018\n/uni00000018/uni0000001a/uni00000011/uni00000017/uni0000001b\n/uni00000018/uni00000014/uni00000011/uni00000013/uni00000015\n/uni00000017/uni00000018/uni00000011/uni00000013/uni00000013/uni00000017/uni00000018/uni00000011/uni0000001a/uni00000017\n/uni00000017/uni00000016/uni00000011/uni00000017/uni00000014\n/uni00000017/uni00000014/uni00000011/uni00000014/uni0000001b\n/uni00000018/uni00000018/uni00000011/uni00000015/uni00000017\n/uni00000017/uni0000001c/uni00000011/uni00000015/uni00000014\n/uni00000017/uni00000016/uni00000011/uni00000018/uni00000013\n/uni00000018/uni00000013/uni00000011/uni0000001a/uni0000001c\n/uni00000017/uni00000019/uni00000011/uni00000015/uni00000014\n/uni00000017/uni00000014/uni00000011/uni0000001a/uni0000001a\n/uni00000014/uni00000013/uni00000008/uni00000018/uni00000013/uni00000008/uni0000001c/uni00000013/uni00000008\n/uni00000033/uni00000048/uni00000055/uni00000046/uni00000048/uni00000051/uni00000057/uni00000003/uni00000052/uni00000049/uni00000003/uni00000050/uni00000048/uni00000057/uni0000004b/uni0000005c/uni0000004f/uni00000044/uni00000057/uni0000004c/uni00000052/uni00000051\n/uni0000001c/uni00000017/uni00000011/uni00000016/uni00000016/uni0000001c/uni00000017/uni00000011/uni00000017/uni0000001b/uni0000001c/uni00000017/uni00000011/uni00000018/uni00000018\n/uni0000001c/uni00000014/uni00000011/uni0000001a/uni00000013/uni0000001c/uni00000014/uni00000011/uni0000001a/uni00000016/uni0000001c/uni00000014/uni00000011/uni0000001a/uni00000019\n/uni00000018/uni00000019/uni00000011/uni0000001b/uni00000019/uni00000018/uni0000001a/uni00000011/uni00000015/uni00000016/uni00000018/uni0000001a/uni00000011/uni00000019/uni0000001b\n/uni00000017/uni00000018/uni00000011/uni0000001a/uni00000017/uni00000017/uni00000018/uni00000011/uni0000001a/uni00000017/uni00000017/uni00000018/uni00000011/uni0000001a/uni00000017\n/uni00000018/uni00000017/uni00000011/uni0000001a/uni00000015/uni00000018/uni00000018/uni00000011/uni00000013/uni00000017/uni00000018/uni00000018/uni00000011/uni00000017/uni00000016\n/uni00000018/uni00000013/uni00000011/uni00000017/uni0000001b/uni00000018/uni00000013/uni00000011/uni0000001a/uni0000001c/uni00000018/uni00000014/uni00000011/uni00000014/uni00000016\n/uni00000024/uni00000035/uni0000003c/uni00000024/uni00000031/uni00000024/uni00000010/uni00000025/uni00000036\n/uni00000025/uni00000036/uni00000030/uni00000024/uni00000033\n/uni00000045/uni0000005a/uni00000044/uni00000010/uni00000050/uni00000048/uni00000057/uni0000004b/uni00000025/uni0000004c/uni00000056/uni00000050/uni00000044/uni00000055/uni0000004e/uni00000025/uni00000036/uni00000025/uni00000052/uni0000004f/uni00000057/uni00000044/uni00000045/uni0000004c/uni00000056/uni00000050/uni00000044/uni0000004f\nFig. 5. Scrutinize of tools against different percent of reads in CpG ‌island and methylationThis figure shows the performance of each tool\nfor different percentages of reads in CpG islands and the percent of methylation in the simulated reads created with the ARYANA read simulator.\nARYANA-BS is better than other tools in all cases.\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\n14 ARYANA-BS\n/uni00000013\n/uni00000015/uni00000018/uni00000013/uni00000013\n/uni00000018/uni00000013/uni00000013/uni00000013\n/uni0000001a/uni00000018/uni00000013/uni00000013\n/uni00000014/uni00000013/uni00000013/uni00000013/uni00000013\n/uni00000014/uni00000015/uni00000018/uni00000013/uni00000013\n/uni00000014/uni00000018/uni00000013/uni00000013/uni00000013\n/uni00000014/uni0000001a/uni00000018/uni00000013/uni00000013/uni00000045/uni0000005a/uni00000044/uni00000010/uni00000050/uni00000048/uni00000057/uni0000004b/uni0000001a/uni0000001a/uni00000011/uni0000001b/uni00000008\n/uni00000014/uni00000019/uni00000011/uni0000001b/uni00000008\n/uni00000017/uni00000011/uni0000001b/uni00000008\n/uni00000024/uni0000004f/uni0000004c/uni0000004a/uni00000051/uni00000048/uni00000047/uni00000003/uni00000052/uni00000051/uni0000004f/uni0000005c/uni00000003/uni00000045/uni0000005c/uni00000003/uni00000024/uni00000035/uni0000003c/uni00000024/uni00000031/uni00000024/uni00000010/uni00000025/uni00000036\n/uni00000024/uni00000035/uni0000003c/uni00000024/uni00000031/uni00000024/uni00000010/uni00000025/uni00000036/uni00000003/uni00000044/uni0000004f/uni0000004c/uni0000004a/uni00000051/uni00000050/uni00000048/uni00000051/uni00000057/uni00000003/uni0000004b/uni00000044/uni00000056/uni00000003/uni0000004f/uni00000052/uni0000005a/uni00000048/uni00000055/uni00000003/uni00000053/uni00000048/uni00000051/uni00000044/uni0000004f/uni00000057/uni0000005c\n/uni00000028/uni00000054/uni00000058/uni00000044/uni0000004f/uni00000003/uni00000044/uni0000004f/uni0000004c/uni0000004a/uni00000051/uni00000050/uni00000048/uni00000051/uni00000057/uni00000003/uni00000053/uni00000048/uni00000051/uni00000044/uni0000004f/uni00000057/uni0000005c\n/uni00000024/uni00000035/uni0000003c/uni00000024/uni00000031/uni00000024/uni00000010/uni00000025/uni00000036/uni00000003/uni00000044/uni0000004f/uni0000004c/uni0000004a/uni00000051/uni00000050/uni00000048/uni00000051/uni00000057/uni00000003/uni0000004b/uni00000044/uni00000056/uni00000003/uni0000004b/uni0000004c/uni0000004a/uni0000004b/uni00000048/uni00000055/uni00000003/uni00000053/uni00000048/uni00000051/uni00000044/uni0000004f/uni00000057/uni0000005c\n/uni00000031/uni00000052/uni00000057/uni00000003/uni00000044/uni0000004f/uni0000004c/uni0000004a/uni00000051/uni00000048/uni00000047/uni00000003/uni00000045/uni0000005c/uni00000003/uni00000024/uni00000035/uni0000003c/uni00000024/uni00000031/uni00000024/uni00000010/uni00000025/uni00000036\n/uni00000013\n/uni00000014/uni00000013/uni00000013/uni00000013/uni00000013\n/uni00000015/uni00000013/uni00000013/uni00000013/uni00000013\n/uni00000016/uni00000013/uni00000013/uni00000013/uni00000013\n/uni00000017/uni00000013/uni00000013/uni00000013/uni00000013/uni00000025/uni00000036/uni00000030/uni00000024/uni00000033\n/uni00000015/uni0000001c/uni00000011/uni00000017/uni00000008\n/uni0000001b/uni00000011/uni00000013/uni00000008\n/uni00000018/uni00000013/uni00000011/uni00000019/uni00000008\n/uni00000014/uni00000015/uni00000011/uni00000013/uni00000008\n/uni00000013\n/uni00000015/uni00000018/uni00000013\n/uni00000018/uni00000013/uni00000013\n/uni0000001a/uni00000018/uni00000013\n/uni00000014/uni00000013/uni00000013/uni00000013\n/uni00000014/uni00000015/uni00000018/uni00000013\n/uni00000014/uni00000018/uni00000013/uni00000013\n/uni00000014/uni0000001a/uni00000018/uni00000013/uni00000044/uni00000045/uni0000004c/uni00000056/uni00000050/uni00000044/uni0000004f\n/uni0000001c/uni00000018/uni00000011/uni00000013/uni00000008\n/uni00000017/uni00000011/uni00000014/uni00000008\n/uni00000010/uni00000015/uni0000001a/uni00000015/uni00000010/uni00000014/uni00000016/uni00000019/uni00000013/uni00000014/uni00000016/uni00000019/uni00000015/uni0000001a/uni00000015/uni00000017/uni00000013/uni0000001b/uni00000018/uni00000017/uni00000017/uni00000019/uni0000001b/uni00000013/uni0000001b/uni00000014/uni00000019/uni0000001c/uni00000018/uni00000015\n/uni00000033/uni00000048/uni00000051/uni00000044/uni0000004f/uni00000057/uni0000005c/uni00000003/uni00000047/uni0000004c/uni00000049/uni00000049/uni00000048/uni00000055/uni00000048/uni00000051/uni00000057/uni0000004c/uni00000044/uni00000057/uni0000004c/uni00000052/uni00000051/uni00000003/uni00000045/uni00000048/uni00000057/uni0000005a/uni00000048/uni00000048/uni00000051\n/uni00000052/uni00000057/uni0000004b/uni00000048/uni00000055/uni00000003/uni00000057/uni00000052/uni00000052/uni0000004f/uni00000056/uni00000003/uni00000044/uni00000051/uni00000047/uni00000003/uni00000024/uni00000035/uni0000003c/uni00000024/uni00000031/uni00000024/uni00000010/uni00000025/uni00000036/uni00000003/uni0000000b/uni00000055/uni00000048/uni00000044/uni00000047/uni00000056/uni00000003/uni00000046/uni00000052/uni00000058/uni00000051/uni00000057/uni0000000c\n/uni00000013\n/uni00000015/uni00000013/uni00000013/uni00000013\n/uni00000017/uni00000013/uni00000013/uni00000013\n/uni00000019/uni00000013/uni00000013/uni00000013\n/uni0000001b/uni00000013/uni00000013/uni00000013\n/uni00000014/uni00000013/uni00000013/uni00000013/uni00000013\n/uni00000014/uni00000015/uni00000013/uni00000013/uni00000013/uni00000025/uni00000036/uni00000025/uni00000052/uni0000004f/uni00000057\n/uni00000033/uni00000048/uni00000055/uni00000046/uni00000048/uni00000051/uni00000057/uni00000003/uni00000052/uni00000049/uni00000003/uni00000055/uni00000048/uni00000044/uni00000047/uni00000056/uni00000003/uni00000045/uni00000044/uni00000056/uni00000048/uni00000047/uni00000003/uni00000052/uni00000051\n/uni00000053/uni00000048/uni00000051/uni00000044/uni0000004f/uni00000057/uni0000005c/uni00000003/uni00000047/uni0000004c/uni00000049/uni00000049/uni00000048/uni00000055/uni00000048/uni00000051/uni00000057/uni0000004c/uni00000044/uni00000057/uni0000004c/uni00000052/uni00000051\n/uni00000019/uni00000011/uni0000001c/uni00000008\n/uni0000001a/uni0000001a/uni00000011/uni00000019/uni00000008\n/uni00000014/uni00000015/uni00000011/uni00000014/uni00000008\n/uni00000016/uni00000011/uni00000017/uni00000008\nFig. 6. Comparison of ARYANA-BS against bwa-meth, BSMAP, abismal, and BSBolt with real data We used the read alignment penalty\nto compare the tools with real data to determine the alignment quality of each tool. For this comparison, we have calculated the penalty for each tool on\neach read and the differentiation between the ARYANA-BS alignment penalty and the other tool’s penalty. In this figure, we have indicated the count\nof reads with each differentiation and the number of reads that were aligned only by ARYANA-BS or the other tool. Note: the box chart was trimmed\nto avoid large plots. Additionally, the reads with equal alignment penalties omitted from the box chart.\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\nARYANA-BS 15\n           A\nTTCGTTTGTGTA\n           ACTCGTGTCCGTGCA                                             ACTCGT\nATCCATACA\n                       ACTC\nATATCCATACA\n                      ATT\nTGTGTTTGTGTA            \nGenome b’Genome a\nGenome c’\nGenome c\nGenome b\nLikely G => \nAAGGTAGAGCATAGGTAAGCAT\nAll G => A\nLikely C => \nT\nAll C => T\nOriginal\nCCATACATGAGTATAGG\nAGTATAGG\nTAAACACAA\nAACATCTA\nAACACA\nATTTGT\nGTGTA\nGCACA\nCAGGCAC\nGTGTCCGTGC\nFig. 7. Context-aware different indexes for the ARYANA-BS seed finding algorithm . Genome a: original reference genome. Genome b:\nall cytosines that are expected to be unmethylated, according to the prior context information, are converted to thymines. Genome c: all cytosines,\nregardless of their contexts, are converted to thymines. Genomes b’ and c’: similar to genomes b and c, by converting guanines to adenines\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint \n\n16 ARYANA-BS\nIndex a\nIndex b\nIndex b'\nIndex c\nread 9\nread 7\nread 4\nread 5\nread 6\nread 1\nread 2\nread 3\nread 6\nread 8\nIndex c'\nread 10\nread 9\nread 7\nread 4\nread 5\nread 6\nread 1\nread 2\nread 3\nread 6\nread 8\nread 10\n1 0.75 0.2 0.86 1\nb a b' b b b b' b' c c'\nE-Step\nM-Step\nFig. 8. The EM-step of ARYANA-BS. In the expectation step, the probability of cytosine methylation at each site, denoted as the latent variable\nZ, is determined based on the alignment specified in ˆθk. Subsequently, in the maximization step, the best index for the placement of each read is\ndetermined based on the probability of cytosine methylation at each cytosine site, utilizing the equation 3.\n.CC-BY 4.0 International licenseperpetuity. It is made available under a \npreprint (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in \nThe copyright holder for thisthis version posted January 23, 2024. ; https://doi.org/10.1101/2024.01.20.576080doi: bioRxiv preprint","source_license":"CC-BY-4.0","license_restricted":false}