近年來，長讀長定序與基因組組裝技術持續進步，使高連續性的基因組組裝結果越來越容易取得。這類資料讓比較基因體學、組裝結果驗證、泛基因組分析，以及以組裝結果為基礎的變異分析更加可行，也使得組裝體對組裝體比對成為後續分析流程中的重要基礎步驟。
雖然 minimap2 已廣泛應用於長讀長比對與組裝層級的序列比較，而 mm2-plus 也進一步提升了 minimap2 在 CPU 上的執行效率，但在處理高連續性的組裝體資料時，部分內部流程仍可能成為新的效能瓶頸。其主要原因在於，組裝體對組裝體比對通常只包含少數幾條很長的查詢序列，因此單純依靠查詢序列層級的平行化，未必能充分利用所有 CPU 執行緒。此外，單一長查詢序列可能產生大量錨點資料，使排序、鏈結、鏈結結果整理，以及比對後處理等內部步驟累積出明顯的執行時間成本。因此，本文的目標並不是重新設計比對演算法，而是在保留原始比對結果的前提下，針對 mm2-plus 內部仍然耗時的部分進行實作層級的加速。
本文主要提出三項加速。第一，使用 stable parallel LSD radix sort 取代原本以比較為基礎的穩定排序流程，以降低大量錨點資料在固定長度 64-bit 排序鍵上的排序成本。第二，在鏈結階段中引入考慮座標間距的工作切分策略，利用參考序列邊界與較大的座標間距，將過大的錨點群組切分為更適合平行處理的子區塊，並透過最小子區塊大小限制避免過度切分。第三，針對比對階段中的序列反轉、連續匹配區段偵測、CIGAR 中匹配與不匹配位置的修正，以及長間距區段收集等局部操作進行加速，以減少重複的逐位元組掃描與不必要的局部運算成本。
實驗結果顯示，加速版本相較於 minimap2 與 mm2-plus 皆能降低整體執行時間。同時，本文透過 PAF 檔案比對確認輸出結果保持一致，說明所提出的方法能在維持原有比對行為的前提下，進一步改善組裝體對組裝體基因組比對的整體執行效能。

Recent years, advances in long-read sequencing and genome assembly technologies have made high-contiguity genome assemblies increasingly accessible. These data have enabled comparative genomics, assembly validation, pangenome analysis, and assembly-based variant analysis to become more feasible, while also making assembly-to-assembly alignment an important foundational step in downstream analyses.
Although minimap2 has been widely used for long-read mapping and assembly-level sequence comparison, and mm2-plus further improves the CPU execution efficiency of minimap2, some pipeline stages may still become new performance bottlenecks when processing high-contiguity assemblies. This is because assembly-to-assembly alignment usually involves only a small number of very long query sequences, meaning that query-level parallelism may not fully utilize all available CPU threads. In addition, a single long query can generate a large number of anchors, causing internal steps such as sorting, chaining, chain organization, and alignment post-processing to accumulate noticeable runtime overhead. Therefore, the goal of this thesis is not to redesign the alignment algorithm, but to perform implementation-level optimization on the remaining time-consuming components inside mm2-plus while preserving the original alignment results.
This thesis mainly proposes three optimizations. First, a stable parallel LSD radix sort is used to replace the original comparison-based stable sorting routine, reducing the large-scale anchor sorting overhead on fixed-width 64-bit sorting keys. Second, a gap-aware workload partitioning strategy is introduced in the chaining stage. This strategy uses reference sequence boundaries and large coordinate gaps to divide oversized anchor groups into components that are more suitable for parallel processing, while applying a minimum component size constraint to avoid excessive partitioning. Third, several local operations in the alignment stage, including sequence reversal, match run detection, CIGAR match/mismatch refinement, and long gap collection, are optimized to reduce repeated byte-wise scanning and unnecessary local overhead.
Experimental results show that the optimized version reduces runtime compared with both minimap2 and mm2-plus. Meanwhile, comparisons of PAF files confirm that the output results remain consistent, demonstrating that the proposed methods can further improve the end-to-end runtime performance of assembly-to-assembly genome alignment while preserving the original alignment behavior.

[1] A. Rhie, S. A. McCarthy, O. Fedrigo, J. Damas, G. Formenti, S. Koren, M. Uliano-Silva, W. Chow, A. Fungtammasan, J. Kim, C. Lee, B. J. Ko, M. Chaisson, G. L. Gedman, L. J. Cantin, F. Thibaud-Nissen, L. Haggerty, I. Bista, M. Smith, B. Haase, J. Mountcastle, S. Winkler, S. Paez, J. Howard, S. C. Vernes, T. M. Lama, F. Grutzner, W. C. Warren, C. N. Balakrishnan, D. Burt, J. M. George, M. T. Biegler, D. Iorns, A. Digby, D. Eason, B. Robertson, T. Edwards, M. Wilkinson, G. Turner, A. Meyer, A. F. Kautt, P. Franchini, H. W. Detrich III, H. Svardal, M. Wagner, G. J. P. Naylor, M. Pippel, M. Malinsky, M. Mooney, M. Simbirsky, B. T. Hannigan, T. Pesout, M. Houck, A. Misuraca, S. B. Kingan, R. Hall, Z. Kronenberg, I. Sović, C. Dunn, Z. Ning, A. Hastie, J. Lee, S. Selvaraj, R. E. Green, N. H. Putnam, I. Gut, J. Ghurye, E. Garrison, Y. Sims, J. Collins, S. Pelan, J. Torrance, A. Tracey, J. Wood, R. E. Dagnew, D. Guan, S. E. London, D. F. Clayton, C. V. Mello, S. R. Friedrich, P. V. Lovell, E. Osipova, F. O. Al-Ajli, S. Secomandi, H. Kim, C. Theofanopoulou, M. Hiller, Y. Zhou, R. S. Harris, K. D. Makova, P. Medvedev, J. Hoffman, P. Masterson, K. Clark, F. Martin, K. Howe, P. Flicek, B. P. Walenz, W. Kwak, H. Clawson, M. Diekhans, L. Nassar, B. Paten, R. H. S. Kraus, A. J. Crawford, M. T. P. Gilbert, G. Zhang, B. Venkatesh, R. W. Murphy, K.-P. Koepfli, B. Shapiro, W. E. Johnson, F. D. Palma, T. Marques-Bonet, E. C. Teeling, T. Warnow, J. M. Graves, O. A. Ryder, D. Haussler, S. J. O’Brien, J. Korlach, H. A. Lewin, K. Howe, E. W. Myers, R. Durbin, A. M. Phillippy, and E. D. Jarvis, “Towards complete and error-free genome assemblies of all vertebrate species,” Nature, vol. 592, pp. 737–746, 2021. DOI: 10.1038/s41586-021-03451-0.
[2] W.-W. Liao, M. Asri, J. Ebler, D. Doerr, M. Haukness, G. Hickey, S. Lu, J. K. Lucas, J. Monlong, H. J. Abel, S. Buonaiuto, X. H. Chang, H. Cheng, J. Chu, V. Colonna, J. M. Eizenga, X. Feng, C. Fischer, R. S. Fulton, S. Garg, C. Groza, A. Guarracino, W. T. Harvey, S. Heumos, K. Howe, M. Jain, T.-Y. Lu, C. Markello, F. J. Martin, M. W. Mitchell, K. M. Munson, M. N. Mwaniki, A. M. Novak, H. E. Olsen, T. Pesout, D. Porubsky, P. Prins, J. A. Sibbesen, J. Sirén, C. Tomlinson, F. Villani, M. R. Vollger, L. L. Antonacci-Fulton, G. Baid, C. A. Baker, A. Belyaeva, K. Billis, A. Carroll, P.-C. Chang, S. Cody, D. E. Cook, R. M. Cook-Deegan, O. E. Cornejo, M. Diekhans, P. Ebert, S. Fairley, O. Fedrigo, A. L. Felsenfeld, G. Formenti, A. Frankish, Y. Gao, N. A. Garrison, C. G. Giron, R. E. Green, L. Haggerty, K. Hoekzema, T. Hourlier, H. P. Ji, E. E. Kenny, B. A. Koenig, A. Kolesnikov, J. O. Korbel, J. Kordosky, S. Koren, H. Lee, A. P. Lewis, H. Magalhães, S. Marco-Sola, P. Marijon, A. McCartney, J. McDaniel, J. Mountcastle, M. Nattestad, S. Nurk, N. D. Olson, A. B. Popejoy, D. Puiu, M. Rautiainen, A. A. Regier, A. Rhie, S. Sacco, A. D. Sanders, V. A. Schneider, B. I. Schultz, K. Shafin, M. W. Smith, H. J. Sofia, A. N. A. Tayoun, F. Thibaud-Nissen, F. F. Tricomi, J. Wagner, B. Walenz, J. M. D. Wood, A. V. Zimin, G. Bourque, M. J. P. Chaisson, P. Flicek, A. M. Phillippy, J. M. Zook, E. E. Eichler, D. Haussler, T. Wang, E. D. Jarvis, K. H. Miga, E. Garrison, T. Marschall, I. M. Hall, H. Li, and B. Paten, “A draft human pangenome reference,” Nature, vol. 617, pp. 312–324, 2023. DOI: 10.1038/s41586-023-05896-x.
[3] G. A. Logsdon, M. R. Vollger, and E. E. Eichler, “Long-read human genome sequencing and its applications,” Nature Reviews Genetics, vol. 21, pp. 597–614, 2020. DOI: 10.1038/s41576-020-0236-x.
[4] K. H. Miga, S. Koren, A. Rhie, M. R. Vollger, A. Gershman, A. Bzikadze, S. Brooks, E. Howe, D. Porubsky, G. A. Logsdon, V. A. Schneider, T. Potapova, J. Wood, W. Chow, J. Armstrong, J. Fredrickson, E. Pak, K. Tigyi, M. Kremitzki, C. Markovic, V. Maduro, A. Dutra, G. G. Bouffard, A. M. Chang, N. F. Hansen, A. B. Wilfert, F. Thibaud-Nissen, A. D. Schmitt, J.-M. Belton, S. Selvaraj, M. Y. Dennis, D. C. Soto, R. Sahasrabudhe, G. Kaya, J. Quick, N. J. Loman, N. Holmes, M. Loose, U. Surti, R. A. Risques, T. A. Graves-Lindsay, R. Fulton, I. Hall, B. Paten, K. Howe, W. Timp, A. Young, J. C. Mullikin, P. A. Pevzner, J. L. Gerton, B. A. Sullivan, E. E. Eichler, and A. M. Phillippy, “Telomere-to-telomere assembly of a complete human X chromosome,” Nature, vol. 585, no. 7823, pp. 79–84, 2020. DOI: 10.1038/s41586-020-2547-7.
[5] S. Nurk, S. Koren, A. Rhie, M. Rautiainen, A. V. Bzikadze, A. Mikheenko, M. R. Vollger, N. Altemose, L. Uralsky, A. Gershman, S. Aganezov, S. J. Hoyt, M. Diekhans, G. A. Logsdon, M. Alonge, S. E. Antonarakis, M. Borchers, G. G. Bouffard, S. Y. Brooks, G. V. Caldas, N.-C. Chen, H. Cheng, C.-S. Chin, W. Chow, L. G. de Lima, P. C. Dishuck, R. Durbin, T. Dvorkina, I. T. Fiddes, G. Formenti, R. S. Fulton, A. Fungtammasan, E. Garrison, P. G. S. Grady, T. A. Graves-Lindsay, I. M. Hall, N. F. Hansen, G. A. Hartley, M. Haukness, K. Howe, M. W. Hunkapiller, C. Jain, M. Jain, E. D. Jarvis, P. Kerpedjiev, M. Kirsche, M. Kolmogorov, J. Korlach, M. Kremitzki, H. Li, V. V. Maduro, T. Marschall, A. M. McCartney, J. McDaniel, D. E. Miller, J. C. Mullikin, E. W. Myers, N. D. Olson, B. Paten, P. Peluso, P. A. Pevzner, D. Porubsky, T. Potapova, E. I. Rogaev, J. A. Rosenfeld, S. L. Salzberg, V. A. Schneider, F. J. Sedlazeck, K. Shafin, C. J. Shew, A. Shumate, Y. Sims, A. F. A. Smit, D. C. Soto, I. Sović, J. M. Storer, A. Streets, B. A. Sullivan, F. Thibaud-Nissen, J. Torrance, J. Wagner, B. P. Walenz, A. Wenger, J. M. D. Wood, C. Xiao, S. M. Yan, A. C. Young, S. Zarate, U. Surti, R. C. McCoy, M. Y. Dennis, I. A. Alexandrov, J. L. Gerton, R. J. O’Neill, W. Timp, J. M. Zook, M. C. Schatz, E. E. Eichler, K. H. Miga, and A. M. Phillippy, “The complete sequence of a human genome,” Science, vol. 376, no. 6588, pp. 44–53, 2022. DOI: 10.1126/science.abj6987.
[6] N. Bray, I. Dubchak, and L. Pachter, “AVID: A global alignment program,” Genome Research, vol. 13, no. 1, pp. 97–102, 2003. DOI: 10.1101/gr.789803.
[7] T. F. Smith and M. S. Waterman, “Identification of common molecular subsequences,” Journal of Molecular Biology, vol. 147, no. 1, pp. 195–197, 1981. DOI: 10.1016/0022-2836(81)90087-5.
[8] R. S. Harris, “Improved pairwise alignment of genomic DNA,” Ph.D. dissertation, The Pennsylvania State University, 2007.
[9] S. M. Kiełbasa, R. Wan, K. Sato, P. Horton, and M. C. Frith, “Adaptive seeds tame genomic sequence comparison,” Genome Research, vol. 21, no. 3, pp. 487–493, 2011. DOI: 10.1101/gr.113985.110.
[10] H. Li, “Minimap2: pairwise alignment for nucleotide sequences,” Bioinformatics, vol. 34, no. 18, pp. 3094–3100, 2018. DOI: 10.1093/bioinformatics/bty191.
[11] H.-N. Lin and W.-L. Hsu, “GSAlign: an efficient sequence alignment tool for intraspecies genomes,” BMC Genomics, vol. 21, no. 1, p. 182, 2020. DOI: 10.1186/s12864-020-6569-1.
[12] B. Song, E. S. Buckler, and M. C. Stitzer, “New whole-genome alignment tools are needed for tapping into plant diversity,” Trends in Plant Science, vol. 29, no. 3, pp. 355–369, 2024. DOI: 10.1016/j.tplants.2023.08.013.
[13] B. Paten, M. Diekhans, D. Earl, J. S. John, J. Ma, B. Suh, and D. Haussler, “Cactus graphs for genome comparisons,” Journal of Computational Biology, vol. 18, no. 3, pp. 469–481, 2011. DOI: 10.1089/cmb.2010.0252.
[14] M. Roberts, W. Hayes, B. R. Hunt, S. M. Mount, and J. A. Yorke, “Reducing storage requirements for biological sequence comparison,” Bioinformatics, vol. 20, no. 18, pp. 3363–3369, 2004. DOI: 10.1093/bioinformatics/bth408.
[15] M. Brudno, C. B. Do, G. M. Cooper, M. F. Kim, E. Davydov, NISC Comparative Sequencing Program, E. D. Green, A. Sidow, and S. Batzoglou, “LAGAN and Multi-LAGAN: Efficient tools for large-scale multiple alignment of genomic DNA,” Genome Research, vol. 13, no. 4, pp. 721–731, 2003. DOI: 10.1101/gr.926603.
[16] W. J. Kent, “BLAT—The BLAST-Like Alignment Tool,” Genome Research, vol. 12, no. 4, pp. 656–664, 2002. DOI: 10.1101/gr.229202.
[17] G. Marçais, A. L. Delcher, A. M. Phillippy, R. Coston, S. L. Salzberg, and A. V. Zimin, “MUMmer4: A fast and versatile genome alignment system,” PLoS Computational Biology, vol. 14, no. 1, e1005944, 2018. DOI: 10.1371/journal.pcbi.1005944.
[18] M. I. Abouelhoda and E. Ohlebusch, “Chaining algorithms for multiple genome comparison,” Journal of Discrete Algorithms, vol. 3, no. 2–4, pp. 321–341, 2005. DOI: 10.1016/j.jda.2004.08.011.
[19] H. Li, “New strategies to improve minimap2 alignment accuracy,” Bioinformatics, vol. 37, no. 23, pp. 4572–4574, 2021. DOI: 10.1093/bioinformatics/btab705.
[20] C. Jain, D. Gibney, and S. V. Thankachan, “Algorithms for colinear chaining with overlaps and gap costs,” Journal of Computational Biology, vol. 29, no. 11, pp. 1237–1251, 2022. DOI: 10.1089/cmb.2022.0266.
[21] G. Chandra, M. Vasimuddin, S. Misra, and C. Jain, “Accelerating minimap2 for whole-genome alignment,” Bioinformatics, vol. 42, no. 3, btag083, 2026. DOI: 10.1093/bioinformatics/btag083.
[22] S. Kalikar, C. Jain, M. Vasimuddin, and S. Misra, “Accelerating minimap2 for long-read sequencing applications on modern CPUs,” Nature Computational Science, vol. 2, no. 2, pp. 78–83, 2022. DOI: 10.1038/s43588-022-00201-8.
[23] L. Dagum and R. Menon, “OpenMP: An Industry-Standard API for Shared-Memory Programming,” IEEE Computational Science and Engineering, vol. 5, no. 1, pp. 46–55, 1998. DOI: 10.1109/99.660313.
[24] T. Kalibera and R. E. Jones, “Rigorous Benchmarking in Reasonable Time,” Proceedings of the 2013 International Symposium on Memory Management, ACM, 2013, pp. 63–74. DOI: 10.1145/2464157.2464160.