Minimap2: căn chỉnh cặp cho các chuỗi nucleotide
Tóm tắt
Các tiến bộ gần đây trong công nghệ giải trình tự hứa hẹn cung cấp các đoạn siêu dài khoảng 100 kb trung bình, các đoạn mRNA hoặc cDNA đầy đủ chiều dài với thông lượng cao và các đoạn gen có độ dài trên 100 Mb. Các chương trình căn chỉnh hiện có không thể hoặc không hiệu quả để xử lý dữ liệu như vậy ở quy mô lớn, điều này đặt ra yêu cầu phát triển các thuật toán căn chỉnh mới.
Minimap2 là một chương trình căn chỉnh đa năng để ánh xạ DNA hoặc các chuỗi mRNA dài vào một cơ sở dữ liệu tham chiếu lớn. Nó hoạt động với các đoạn ngắn chính xác có độ dài ≥100 bp, các đoạn gen dài ≥1 kb với tỷ lệ lỗi khoảng 15%, các đoạn RNA thô đầy đủ chiều dài hoặc cDNA và các đoạn lắp ráp hoặc các nhiễm sắc thể đầy đủ liên quan chặt chẽ có độ dài hàng trăm megabases. Minimap2 thực hiện căn chỉnh split-read, sử dụng chi phí khoảng trống lõm cho các chèn và xóa dài và giới thiệu các phương pháp mới để giảm thiểu các căn chỉnh giả. Nó nhanh hơn từ 3–4 lần so với các chương trình căn chỉnh đọc ngắn chính thống với độ chính xác tương đương, và nhanh hơn ≥30 lần so với các chương trình căn chỉnh genomic hoặc cDNA dài với độ chính xác cao hơn, vượt qua hầu hết các chương trình căn chỉnh chuyên biệt cho một loại căn chỉnh.
Từ khóa
Tài liệu tham khảo
Abouelhoda, 2005, Chaining algorithms for multiple genome comparison, J. Discrete Algorithms, 3, 321, 10.1016/j.jda.2004.08.011
Altschul, 1986, Optimal sequence alignment using affine gap costs, Bull. Math. Biol, 48, 603, 10.1016/S0092-8240(86)90010-8
Altschul, 1997, Gapped BLAST and PSI-BLAST: a new generation of protein database search programs, Nucleic Acids Res, 25, 3389, 10.1093/nar/25.17.3389
Berlin, 2015, Assembling large genomes with single-molecule sequencing and locality-sensitive hashing, Nat. Biotechnol, 33, 623, 10.1038/nbt.3238
Byrne, 2017, Nanopore long-read RNAseq reveals widespread transcriptional variation among the surface receptors of individual B cells, Nat. Commun, 8, 16027., 10.1038/ncomms16027
Chaisson, 2012, Mapping single molecule sequencing reads using basic local alignment with successive refinement (BLASR): application and theory, BMC Bioinformatics, 13, 238., 10.1186/1471-2105-13-238
Daily, 2016, Parasail: sIMD C library for global, semi-global, and local pairwise sequence alignments, BMC Bioinformatics, 17, 81., 10.1186/s12859-016-0930-z
Depristo, 2011, A framework for variation discovery and genotyping using next-generation DNA sequencing data, Nat. Genet, 43, 491, 10.1038/ng.806
Dobin, 2013, STAR: ultrafast universal RNA-seq aligner, Bioinformatics, 29, 15, 10.1093/bioinformatics/bts635
Farrar, 2007, Striped Smith-Waterman speeds database searches six times over other SIMD implementations, Bioinformatics, 23, 156, 10.1093/bioinformatics/btl582
Gotoh, 1982, An improved algorithm for matching biological sequences, J. Mol. Biol, 162, 705, 10.1016/0022-2836(82)90398-9
Gotoh, 1990, Optimal sequence alignment allowing for long gaps, Bull. Math. Biol, 52, 359, 10.1007/BF02458577
Holtgrewe, 2010
Irimia, 2008, Evolutionary convergence on highly-conserved 3’ intron structures in intron-poor eukaryotes and insights into the ancestral eukaryotic genome, PLoS Genet, 4, e1000148, 10.1371/journal.pgen.1000148
Iwata, 2012, Benchmarking spliced alignment programs including Spaln2, an extended version of Spaln that incorporates additional species-specific features, Nucleic Acids Res, 40, e161, 10.1093/nar/gks708
Jain, 2018, Nanopore sequencing and assembly of a human genome with ultra-long reads, Nat. Biotechnol., 36, 338, 10.1038/nbt.4060
Li, 2013, Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM, arXiv
Li, 2016, Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences, Bioinformatics, 32, 2103, 10.1093/bioinformatics/btw152
Li, 2010, Fast and accurate long-read alignment with Burrows-Wheeler transform, Bioinformatics, 26, 589, 10.1093/bioinformatics/btp698
Li, 2009, The Sequence Alignment/Map format and SAMtools, Bioinformatics, 25, 2078, 10.1093/bioinformatics/btp352
Li, 2017, New synthetic-diploid benchmark for accurate variant calling evaluation, bioRxiv
Lin, 2017, Kart: a divide-and-conquer algorithm for NGS read alignment, Bioinformatics, 33, 2281, 10.1093/bioinformatics/btx189
Liu, 2016, rHAT: fast alignment of noisy long reads with regional hashing, Bioinformatics, 32, 1625, 10.1093/bioinformatics/btv662
Liu, 2017, LAMSA: fast split read alignment with long approximate matches, Bioinformatics, 33, 192, 10.1093/bioinformatics/btw594
Marçais, 2018, MUMmer4: a fast and versatile genome alignment system, PLoS Comput. Biol, 14, e1005944, 10.1371/journal.pcbi.1005944
Ono, 2013, PBSIM: pacBio reads simulator—toward accurate genome assembly, Bioinformatics, 29, 119, 10.1093/bioinformatics/bts649
Roberts, 2004, Reducing storage requirements for biological sequence comparison, Bioinformatics, 20, 3363, 10.1093/bioinformatics/bth408
Sedlazeck, 2018, Accurate detection of complex structural variations using single-molecule sequencing, Nat. Methods, 10.1038/s41592-018-0001-7
Šošić, 2017, Edlib: a C/C++ library for fast, exact sequence alignment using edit distance, Bioinformatics, 33, 1394, 10.1093/bioinformatics/btw753
Sović, 2016, Fast and sensitive mapping of nanopore sequencing reads with GraphMap, Nat. Commun, 7, 11307., 10.1038/ncomms11307
Suzuki, 2018, Introducing difference recurrence relations for faster semi-global alignment of long sequences, BMC Bioinformatics, 19, 45, 10.1186/s12859-018-2014-8
Wu, 1996, A subquadratic algorithm for approximate limited expression matching, Algorithmica, 15, 50, 10.1007/BF01942606
Wu, 2005, GMAP: a genomic mapping and alignment program for mRNA and EST sequences, Bioinformatics, 21, 1859, 10.1093/bioinformatics/bti310
Zaharia, 2011, Faster and more accurate sequence alignment with SNAP, arXiv, 1111, 5572