Harp: Leveraging Quasi-Sequential Characteristics to Accelerate Sequence-to-Graph Mapping of Long Reads
Authors: 
Yichi Zhang, Dibei Chen, Gang Zeng, Jianfeng Zhu, Zhaoshi Li, Longlong Chen, Shaojun Wei, Leibo LiuAuthors Info & Claims
Pages 512 - 527
Abstract
Read mapping is a crucial task in computational genomics. Recently, there has been a significant paradigm shift from sequence-to-sequence mapping (S2S) to sequence-to-graph mapping (S2G). The S2G mapping incurs high graph processing overheads and leads to an unnoticed shift of performance hotspots. This presents a substantial challenge to current software implementations and hardware accelerators.
This paper introduces Harp, a novel S2G mapping acceleration system. Harp leverages the structural similarities between genome graphs and sequences, significantly reducing graph processing overhead by exploiting their quasi-sequential characteristic. The Harp accelerator is co-designed with two main algorithmic components: (1) HarpTree, a compact data structure that explicitly reveals the quasi-sequential characteristic, enabling simplifications of graph processing algorithms in S2G mapping, and (2) HarpExt, a multi-stage seed-extension algorithm that mitigates graph operation overhead while maintaining the sight of S2G mapping. Harp achieves an average 140× speedup over the latest S2G mapping software and outperforms the state-of-the-art S2G accelerator by 23.6× while reducing the chip area by 72% in S2G mapping of long reads.
References
[1]
Can Alkan, Jeffrey M. Kidd, Tomas Marques-Bonet, Gozde Aksay, Francesca Antonacci, Fereydoun Hormozdiari, Jacob O. Kitzman, Carl Baker, Maika Malig, Onur Mutlu, S. Cenk Sahinalp, Richard A. Gibbs, and Evan E. Eichler. 2009. Personalized copy number and segmental duplication maps using next-generation sequencing. Nature Genetics 41, 10 (Oct. 2009), 1061--1067.
[2]
Mohammed Alser, Joel Lindegger, Can Firtina, Nour Almadhoun, Haiyu Mao, Gagandeep Singh, Juan Gomez-Luna, and Onur Mutlu. 2022. From molecules to genomic variations: Accelerating genome analysis via intelligent algorithms and architectures. Computational and Structural Biotechnology Journal 20 (Jan. 2022), 4579--4599.
[3]
Kristian G. Andersen, B. Jesse Shapiro, Christian B. Matranga, Rachel Sealfon, Aaron E. Lin, Lina M. Moses, Onikepe A. Folarin, Augustine Goba, Ikponmwonsa Odia, Philomena E. Ehiane, Mambu Momoh, Eleina M. England, Sarah Winnicki, Luis M. Branco, Stephen K. Gire, Eric Phelan, Ridhi Tariyal, Ryan Tewhey, Omowunmi Omoniwa, Mohammed Fullah, Richard Fonnie, Mbalu Fonnie, Lansana Kanneh, Simbirie Jalloh, Michael Gbakie, Sidiki Saffa, Kandeh Karbo, Adrianne D. Gladden, James Qu, Matthew Stremlau, Mahan Nekoui, Hilary K. Finucane, Shervin Tabrizi, Joseph J. Vitti, Bruce Birren, Michael Fitzgerald, Caryn McCowan, Andrea Ireland, Aaron M. Berlin, James Bochicchio, Barbara Tazon-Vega, Niall J. Lennon, Elizabeth M. Ryan, Zach Bjornson, Danny A. Milner, Amanda K. Lukens, Nisha Broodie, Megan Rowland, Megan Heinrich, Marjan Akdag, John S. Schieffelin, Danielle Levy, Henry Akpan, Daniel G. Bausch, Kathleen Rubins, Joseph B. McCormick, Eric S. Lander, Stephan Günther, Lisa Hensley, Sylvanus Okogbenin, Viral Hemorrhagic Fever Consortium, Stephen F. Schaffner, Peter O. Okokhere, S. Humarr Khan, Donald S. Grant, George O. Akpede, Danny A. Asogun, Andreas Gnirke, Joshua Z. Levin, Christian T. Happi, Robert F. Garry, and Pardis C. Sabeti. 2015. Clinical Sequencing Uncovers Origins and Evolution of Lassa Virus. Cell 162, 4 (Aug. 2015), 738--750.
[4]
Euan A. Ashley. 2016. Towards precision medicine. Nature Reviews. Genetics 17, 9 (Aug. 2016), 507--522.
[5]
Gunjan Baid, Daniel E. Cook, Kishwar Shafin, Taedong Yun, Felipe Llinares-López, Quentin Berthet, Anastasiya Belyaeva, Armin Töpfer, Aaron M. Wenger, William J. Rowell, Howard Yang, Alexey Kolesnikov, Waleed Ammar, Jean-Philippe Vert, Ashish Vaswani, Cory Y. McLean, Maria Nattestad, Pi-Chuan Chang, and Andrew Carroll. 2023. Deep-Consensus improves the accuracy of sequences with a gap-aware sequence transformer. Nature Biotechnology 41, 2 (Feb. 2023), 232--238.
[6]
Ljiljana Brankovic, Costas S. Iliopoulos, Ritu Kundu, Manal Mohamed, Solon P. Pissis, and Fatima Vayani. 2016. Linear-time superbubble identification algorithm for genome assembly. Theoretical Computer Science 609 (2016), 374--383.
[7]
Damla Senol Cali, Gurpreet S. Kalsi, Zülal Bingöl, Can Firtina, Lavanya Subramanian, Jeremie S. Kim, Rachata Ausavarungnirun, Mohammed Alser, Juan Gomez-Luna, Amirali Boroumand, Anant Norion, Allison Scibisz, Sreenivas Subramoneyon, Can Alkan, Saugata Ghose, and Onur Mutlu. 2020. GenASM: A High-Performance, Low-Power Approximate String Matching Acceleration Framework for Genome Sequence Analysis. In 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO). 951--966.
[8]
Damla Senol Cali, Konstantinos Kanellopoulos, Joël Lindegger, Zülal Bingöl, Gurpreet S. Kalsi, Ziyi Zuo, Can Firtina, Meryem Banu Cavlak, Jeremie Kim, Nika Mansouri Ghiasi, Gagandeep Singh, Juan Gómez-Luna, Nour Almadhoun Alserr, Mohammed Alser, Sreenivas Subramoney, Can Alkan, Saugata Ghose, and Onur Mutlu. 2022. SeGraM: a universal hardware accelerator for genomic sequence-to-graph and sequence-to-sequence mapping. In Proceedings of the 49th Annual International Symposium on Computer Architecture (ISCA '22). Association for Computing Machinery, New York, NY, USA, 638--655.
[9]
Isaac S. Chan and Geoffrey S. Ginsburg. 2011. Personalized medicine: progress and promise. Annual Review of Genomics and Human Genetics 12 (2011), 217--244.
[10]
Xian Chang, Jordan Eizenga, Adam M Novak, Jouni Sirén, and Benedict Paten. 2020. Distance indexing and seed clustering in sequence graphs. Bioinformatics 36, Supplement_1 (July 2020), i146--i153.
[11]
Sai Chen, Peter Krusche, Egor Dolzhenko, Rachel M. Sherman, Roman Petrovski, Felix Schlesinger, Melanie Kirsche, David R. Bentley, Michael C. Schatz, Fritz J. Sedlazeck, and Michael A. Eberle. 2019. Paragraph: a graph-based structural variant genotyper for short-read sequence data. Genome Biology 20, 1 (Dec. 2019), 291.
[12]
Xiaomin Chen, Yutong Kang, Jing Luo, Kun Pang, Xin Xu, Jinyu Wu, Xiaokun Li, and Shengwei Jin. 2021. Next-Generation Sequencing Reveals the Progression of COVID-19. Frontiers in Cellular and Infection Microbiology 11 (2021), 632490.
[13]
Lynda Chin, Jannik N. Andersen, and P. Andrew Futreal. 2011. Cancer genomics: from discovery science to personalized medicine. Nature Medicine 17, 3 (March 2011), 297--303.
[14]
Laura Clarke, Susan Fairley, Xiangqun Zheng-Bradley, Ian Streeter, Emily Perry, Ernesto Lowy, Anne-Marie Tassé, and Paul Flicek. 2017. The international Genome sample resource (IGSR): A worldwide collection of genome variation incorporating the 1000 Genomes Project data. Nucleic Acids Research 45, D1 (2017), D854--D859.
[15]
Vidushi Dadu, Sihao Liu, and Tony Nowatzki. 2021. PolyGraph: Exposing the Value of Flexibility for Graph Processing Accelerators. In 2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA). 595--608.
[16]
Zonghao Feng and Qiong Luo. 2021. Accelerating Sequence-to-Graph Alignment on Heterogeneous Processors. In 50th International Conference on Parallel Processing. Association for Computing Machinery, New York, NY, USA, 1--10.
[17]
T. Friedmann. 1989. Progress toward human gene therapy. Science (New York, N.Y.) 244, 4910 (June 1989), 1275--1281.
[18]
Daichi Fujiki, Arun Subramaniyan, Tianjun Zhang, Yu Zeng, Reetuparna Das, David Blaauw, and Satish Narayanasamy. 2018. GenAx: A Genome Sequencing Accelerator. In 2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA). 69--82.
[19]
Daichi Fujiki, Shunhao Wu, Nathan Ozog, Kush Goliya, David Blaauw, Satish Narayanasamy, and Reetuparna Das. 2020. SeedEx: A Genome Sequencing Accelerator for Optimal Alignments in Subminimal Space. In 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO). 937--950.
[20]
Erik Garrison, Jouni Sirén, Adam M. Novak, Glenn Hickey, Jordan M. Eizenga, Eric T. Dawson, William Jones, Shilpa Garg, Charles Markello, Michael F. Lin, Benedict Paten, and Richard Durbin. 2018. Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nature Biotechnology 36, 9 (2018), 875--879.
[21]
Geoffrey S. Ginsburg and Huntington F. Willard. 2009. Genomic and personalized medicine: foundations and applications. Translational Research: The Journal of Laboratory and Clinical Medicine 154, 6 (Dec. 2009), 277--287.
[22]
Jennifer L. Gori, Patrick D. Hsu, Morgan L. Maeder, Shen Shen, G. Grant Welstead, and David Bumcrot. 2015. Delivery and Specificity of CRISPR-Cas9 Genome Editing Technologies for Human Gene Therapy. Human Gene Therapy 26, 7 (July 2015), 443--451.
[23]
Licheng Guo, Jason Lau, Zhenyuan Ruan, Peng Wei, and Jason Cong. 2019. Hardware Acceleration of Long Read Pairwise Overlapping in Genome Sequencing: A Race Between FPGA and GPU. In 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). 127--135.
[24]
S. Hacein-Bey-Abina, C. Von Kalle, M. Schmidt, M. P. McCormack, N. Wulffraat, P. Leboulch, A. Lim, C. S. Osborne, R. Pawliuk, E. Morillon, R. Sorensen, A. Forster, P. Fraser, J. I. Cohen, G. de Saint Basile, I. Alexander, U. Wintergerst, T. Frebourg, A. Aurias, D. Stoppa-Lyonnet, S. Romana, I. Radford-Weiss, F. Gross, F. Valensi, E. Delabesse, E. Macintyre, F. Sigaux, J. Soulier, L. E. Leiva, M. Wissler, C. Prinz, T. H. Rabbitts, F. Le Deist, A. Fischer, and M. Cavazzana-Calvo. 2003. LMO2-associated clonal T cell proliferation in two patients after gene therapy for SCID-X1. Science (New York, N.Y.) 302, 5644 (Oct. 2003), 415--419.
[25]
Margaret A. Hamburg and Francis S. Collins. 2010. The path to personalized medicine. The New England Journal of Medicine 363, 4 (July 2010), 301--304.
[26]
Glenn Hickey, David Heller, Jean Monlong, Jonas A. Sibbesen, Jouni Sirén, Jordan Eizenga, Eric T. Dawson, Erik Garrison, Adam M. Novak, and Benedict Paten. 2020. Genotyping structural variants in pangenome graphs using the vg toolkit. Genome Biology 21, 1 (Feb. 2020), 35.
[27]
Wenqin Huangfu, Xueqi Li, Shuangchen Li, Xing Hu, Peng Gu, and Yuan Xie. 2019. MEDAL: Scalable DIMM based Near Data Processing Accelerator for DNA Seeding Algorithm. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO '52). Association for Computing Machinery, New York, NY, USA, 587--599.
[28]
Costas S. Iliopoulos, Ritu Kundu, Manal Mohamed, and Fatima Vayani. 2016. Popping Superbubbles and Discovering Clumps: Recent Developments in Biological Sequence Analysis. In WALCOM: Algorithms and Computation (Lecture Notes in Computer Science), Mohammad Kaykobad and Rossella Petreschi (Eds.). Springer International Publishing, Cham, 3--14.
[29]
Pesho Ivanov, Benjamin Bichsel, Harun Mustafa, André Kahles, Gunnar Rätsch, and Martin Vechev. 2020. AStarix: Fast and Optimal Sequence-to-Graph Alignment. In Research in Computational Molecular Biology (Lecture Notes in Computer Science), Russell Schwartz (Ed.). Springer International Publishing, Cham, 104--119.
[30]
Chirag Jain, Sanchit Misra, Haowen Zhang, Alexander Dilthey, and Srinivas Aluru. 2019. Accelerating Sequence Alignment to Graphs. In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 451--461.
[31]
Saurabh Kalikar, Chirag Jain, Md Vasimuddin, and Sanchit Misra. 2022. Accelerating minimap2 for long-read sequencing applications on modern CPUs. Nature Computational Science 2, 2 (Feb. 2022), 78--83.
[32]
Daehwan Kim, Joseph M. Paggi, Chanhee Park, Christopher Bennett, and Steven L. Salzberg. 2019. Graph-based genome alignment and genotyping with HISAT2 and HISAT-genotype. Nature Biotechnology 37, 8 (Aug. 2019), 907--915.
[33]
Athanasios Kousathanas, Erola Pairo-Castineira, Konrad Rawlik, Alex Stuckey, Christopher A. Odhams, Susan Walker, Clark D. Russell, Tomas Malinauskas, Yang Wu, Jonathan Millar, Xia Shen, Katherine S. Elliott, Fiona Griffiths, Wilna Oosthuyzen, Kirstie Morrice, Sean Keating, Bo Wang, Daniel Rhodes, Lucija Klaric, Marie Zechner, Nick Parkinson, Afshan Siddiq, Peter Goddard, Sally Donovan, David Maslove, Alistair Nichol, Malcolm G. Semple, Tala Zainy, Fiona Maleady-Crowe, Linda Todd, Shahla Salehi, Julian Knight, Greg Elgar, Georgia Chan, Prabhu Arumugam, Christine Patch, Augusto Rendon, David Bentley, Clare Kingsley, Jack A. Kosmicki, Julie E. Horowitz, Aris Baras, Goncalo R. Abecasis, Manuel A. R. Ferreira, Anne Justice, Tooraj Mirshahi, Matthew Oetjens, Daniel J. Rader, Marylyn D. Ritchie, Anurag Verma, Tom A. Fowler, Manu Shankar-Hari, Charlotte Summers, Charles Hinds, Peter Horby, Lowell Ling, Danny McAuley, Hugh Montgomery, Peter J. M. Openshaw, Paul Elliott, Timothy Walsh, Albert Tenesa, GenOMICC investigators, 23andMe investigators, COVID-19 Human Genetics Initiative, Angie Fawkes, Lee Murphy, Kathy Rowan, Chris P. Ponting, Veronique Vitart, James F. Wilson, Jian Yang, Andrew D. Bretherick, Richard H. Scott, Sara Clohisey Hendry, Loukas Moutsianas, Andy Law, Mark J. Caulfield, and J. Kenneth Baillie. 2022. Whole-genome sequencing reveals host factors underlying critical COVID-19. Nature 607, 7917 (July 2022), 97--103.
[34]
Heng Li. 2018. Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics 34, 18 (Sept. 2018), 3094--3100.
[35]
Heng Li, Xiaowen Feng, and Chong Chu. 2020. The design and construction of reference pangenome graphs with minigraph. Genome Biology 21, 1 (Oct. 2020), 265.
[36]
Ernesto Lowy-Gallego, Susan Fairley, Xiangqun Zheng-Bradley, Magali Ruffier, Laura Clarke, Paul Flicek, and The 1000 Genomes Project Consortium. 2020. Variant calling on the GRCh38 assembly with the data from phase three of the 1000 Genomes Project. Technical Report 4:50. Wellcome Open Research.
[37]
Marco A. Marra, Steven J. M. Jones, Caroline R. Astell, Robert A. Holt, Angela Brooks-Wilson, Yaron S. N. Butterfield, Jaswinder Khattra, Jennifer K. Asano, Sarah A. Barber, Susanna Y. Chan, Alison Cloutier, Shaun M. Coughlin, Doug Freeman, Noreen Girn, Obi L. Griffith, Stephen R. Leach, Michael Mayo, Helen McDonald, Stephen B. Montgomery, Pawan K. Pandoh, Anca S. Petrescu, A. Gordon Robertson, Jacqueline E. Schein, Asim Siddiqui, Duane E. Smailus, Jeff M. Stott, George S. Yang, Francis Plummer, Anton Andonov, Harvey Artsob, Nathalie Bastien, Kathy Bernard, Timothy F. Booth, Donnie Bowness, Martin Czub, Michael Drebot, Lisa Fernando, Ramon Flick, Michael Garbutt, Michael Gray, Allen Grolla, Steven Jones, Heinz Feldmann, Adrienne Meyers, Amin Kabani, Yan Li, Susan Normand, Ute Stroher, Graham A. Tipples, Shaun Tyler, Robert Vogrig, Diane Ward, Brynn Watson, Robert C. Brunham, Mel Krajden, Martin Petric, Danuta M. Skowronski, Chris Upton, and Rachel L. Roper. 2003. The Genome sequence of the SARS-associated coronavirus. Science (New York, N.Y.) 300, 5624 (May 2003), 1399--1404.
[38]
Anirban Nag, C. N. Ramachandra, Rajeev Balasubramonian, Ryan Stutsman, Edouard Giacomin, Hari Kambalasubramanyam, and Pierre-Emmanuel Gaillardon. 2019. GenCache: Leveraging In-Cache Operators for Efficient Sequence Alignment. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO '52). Association for Computing Machinery, New York, NY, USA, 334--346.
[39]
Yukiteru Ono, Kiyoshi Asai, and Michiaki Hamada. 2021. PBSIM2: a simulator for long-read sequencers with a novel generative model of quality scores. Bioinformatics 37, 5 (March 2021), 589--595.
[40]
Yukiteru Ono, Michiaki Hamada, and Kiyoshi Asai. 2022. PBSIM3: a simulator for all types of PacBio and ONT long reads. NAR Genomics and Bioinformatics 4, 4 (Dec. 2022), lqac092.
[41]
Taku Onodera, Kunihiko Sadakane, and Tetsuo Shibuya. 2013. Detecting Superbubbles in Assembly Graphs. In Algorithms in Bioinformatics (Lecture Notes in Computer Science), Aaron Darling and Jens Stoye (Eds.). Springer, Berlin, Heidelberg, 338--348.
[42]
Benedict Paten, Jordan M. Eizenga, Yohei M. Rosen, Adam M. Novak, Erik Garrison, and Glenn Hickey. 2018. Superbubbles, Ultrabubbles, and Cacti. Journal of Computational Biology 25, 7 (July 2018), 649--663.
[43]
Benedict Paten, Adam M. Novak, Jordan M. Eizenga, and Erik Garrison. 2017. Genome graphs and the evolution of genome inference. Genome Research 27, 5 (May 2017), 665--676.
[44]
A. Pfeifer and I. M. Verma. 2001. Gene therapy: promises and problems. Annual Review of Genomics and Human Genetics 2 (2001), 177--211.
[45]
Alan D. Radford, David Chapman, Linda Dixon, Julian Chantrey, Alistair C. Darby, and Neil Hall. 2012. Application of next-generation sequencing technologies in virology. The Journal of General Virology 93, Pt 9 (Sept. 2012), 1853--1868.
[46]
Goran Rakocevic, Vladimir Semenyuk, Wan-Ping Lee, James Spencer, John Browning, Ivan J. Johnson, Vladan Arsenijevic, Jelena Nadj, Kaushik Ghose, Maria C. Suciu, Sun-Gou Ji, Gülfem Demir, Lizao Li, Berke Ç Toptaş, Alexey Dolgoborodov, Björn Pollex, Iosif Spulber, Irina Glotova, Péter Kómár, Andrew L. Stachyra, Yilong Li, Milos Popovic, Morten Källberg, Amit Jain, and Deniz Kural. 2019. Fast and accurate genomic analyses using genome graphs. Nature Genetics 51, 2 (Feb. 2019), 354--362.
[47]
Mikko Rautiainen and Tobias Marschall. 2020. GraphAligner: rapid and versatile sequence-to-graph alignment. Genome Biology 21, 1 (Sept. 2020), 253.
[48]
Harisankar Sadasivan, Milos Maric, Eric Dawson, Vishanth Iyer, Johnny Israeli, and Satish Narayanasamy. 2023. Accelerating Minimap2 for Accurate Long Read Alignment on GPUs. Journal of Biotechnology and Biomedicine 6, 1 (Jan. 2023), 13--23. http://www.fotunejournals.com/accelerating-minimap2-for-accurate-long-read-alignment-on-gpus.html
[49]
Jouni Sirén, Jean Monlong, Xian Chang, Adam M. Novak, Jordan M. Eizenga, Charles Markello, Jonas A. Sibbesen, Glenn Hickey, Pi-Chuan Chang, Andrew Carroll, Namrata Gupta, Stacey Gabriel, Thomas W. Blackwell, Aakrosh Ratan, Kent D. Taylor, Stephen S. Rich, Jerome I. Rotter, David Haussler, Erik Garrison, and Benedict Paten. 2021. Pangenomics enables genotyping of known structural variants in 5202 diverse genomes. Science 374, 6574 (Dec. 2021), abg8871.
[50]
Arun Subramaniyan, Jack Wadden, Kush Goliya, Nathan Ozog, Xiao Wu, Satish Narayanasamy, David Blaauw, and Reetuparna Das. 2021. Accelerated Seeding for Genome Sequence Alignment with Enumerated Radix Trees. In 2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA). 388--401.
[51]
The Computational Pan-Genomics Consortium. 2018. Computational pan-genomics: status, promises and challenges. Briefings in Bioinformatics 19, 1 (Jan. 2018), 118--135.
[52]
Yatish Turakhia, Gill Bejerano, and William J. Dally. 2018. Darwin: A Genomics Co-processor Provides up to 15,000X Acceleration on Long Read Assembly. ACM SIGPLAN Notices 53, 2 (March 2018), 199--213.
[53]
Inder M. Verma and Matthew D. Weitzman. 2005. Gene therapy: twenty-first century medicine. Annual Review of Biochemistry 74 (2005), 711--738.
[54]
Fang Wang, Shujia Huang, Rongsui Gao, Yuwen Zhou, Changxiang Lai, Zhichao Li, Wenjie Xian, Xiaobo Qian, Zhiyu Li, Yushan Huang, Qiyuan Tang, Panhong Liu, Ruikun Chen, Rong Liu, Xuan Li, Xin Tong, Xuan Zhou, Yong Bai, Gang Duan, Tao Zhang, Xun Xu, Jian Wang, Huanming Yang, Siyang Liu, Qing He, Xin Jin, and Lei Liu. 2020. Initial whole-genome sequencing and analysis of the host genetic contribution to COVID-19 severity and susceptibility. Cell Discovery 6, 1 (Nov. 2020), 83.
[55]
Aaron M. Wenger, Paul Peluso, William J. Rowell, Pi-Chuan Chang, Richard J. Hall, Gregory T. Concepcion, Jana Ebler, Arkarachai Fungtammasan, Alexey Kolesnikov, Nathan D. Olson, Armin Töpfer, Michael Alonge, Medhat Mahmoud, Yufeng Qian, Chen-Shan Chin, Adam M. Phillippy, Michael C. Schatz, Gene Myers, Mark A. DePristo, Jue Ruan, Tobias Marschall, Fritz J. Sedlazeck, Justin M. Zook, Heng Li, Sergey Koren, Andrew Carroll, David R. Rank, and Michael W. Hunkapiller. 2019. Accurate circular consensus long-read sequencing improves variant detection and assembly of a human genome. Nature Biotechnology 37, 10 (Oct. 2019), 1155--1162.
[56]
Gang Zeng, Jianfeng Zhu, Yichi Zhang, Ganhui Chen, Zhenhai Yuan, Shaojun Wei, and Leibo Liu. 2024. A High-Performance Genomic Accelerator for Accurate Sequence-to-Graph Alignment Using Dynamic Programming Algorithm. IEEE Transactions on Parallel and Distributed Systems 35, 2 (Feb. 2024), 237--249.
[57]
Daniel R. Zerbino and Ewan Birney. 2008. Velvet: Algorithms for de novo short read assembly using de Bruijn graphs. Genome Research 18, 5 (May 2008), 821--829.
Index Terms
- Harp: Leveraging Quasi-Sequential Characteristics to Accelerate Sequence-to-Graph Mapping of Long Reads
Recommendations
SeGraM: a universal hardware accelerator for genomic sequence-to-graph and sequence-to-sequence mapping
ISCA '22: Proceedings of the 49th Annual International Symposium on Computer ArchitectureA critical step of genome sequence analysis is the mapping of sequenced DNA fragments (i.e., reads) collected from an individual to a known linear reference genome sequence (i.e., sequence-to-sequence mapping). Recent works replace the linear reference ...
REPUTE: an OpenCL based read mapping tool for embedded genomics
DATE '20: Proceedings of the 23rd Conference on Design, Automation and Test in EuropeGenomics is transforming medicine from reactive to personalized, predictive, preventive and participatory (P4). The massive amount of data produced by genomics is a major challenge as it requires extensive computational capabilities, consuming large ...
Mapping RNA-seq reads to transcriptomes efficiently based on learning to hash method
AbstractAccurate and efficient read-alignment is one of the fundamental challenges in RNA-seq analysis. Due to the increasingly large number of reads generated from the RNA-seq experiments, read-alignment is a time-consuming task. Many mappers ...
Graphical abstractDisplay Omitted
Highlights- Learning to hash algorithm is first used to mapping reads to the transcriptome.
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2024
1106 pages
ISBN:9798400703867
DOI:10.1145/3620666
- General Chairs:
- Nael Abu-Ghazaleh,
- Rajiv Gupta,
- Program Chairs:
- Madan Musuvathi,
- Dan Tsafrir
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 27 April 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
ASPLOS '24: 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3
April 27 - May 1, 2024
CA, La Jolla, USA
Acceptance Rates
Overall Acceptance Rate 535 of 2,713 submissions, 20%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 594Total Downloads
- Downloads (Last 12 months)594
- Downloads (Last 6 weeks)100
Reflects downloads up to 01 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in