Debian Codegraph @

bwa-apache2/bwamem.h

raw
1 /* The MIT License
2
3 Copyright (c) 2018- Dana-Farber Cancer Institute
4 2009-2018 Broad Institute, Inc.
5 2008-2009 Genome Research Ltd. (GRL)
6
7 Permission is hereby granted, free of charge, to any person obtaining
8 a copy of this software and associated documentation files (the
9 "Software"), to deal in the Software without restriction, including
10 without limitation the rights to use, copy, modify, merge, publish,
11 distribute, sublicense, and/or sell copies of the Software, and to
12 permit persons to whom the Software is furnished to do so, subject to
13 the following conditions:
14
15 The above copyright notice and this permission notice shall be
16 included in all copies or substantial portions of the Software.
17
18 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
22 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
23 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
24 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
25 SOFTWARE.
26 */
27 #ifndef BWAMEM_H_
28 #define BWAMEM_H_
29
30 #include "bwt.h"
31 #include "bntseq.h"
32 #include "bwa.h"
33 #include "kstring.h"
34
35 #define MEM_MAPQ_COEF 30.0
36 #define MEM_MAPQ_MAX 60
37
38 struct __smem_i;
39 typedef struct __smem_i smem_i;
40
41 #define MEM_F_PE 0x2
42 #define MEM_F_NOPAIRING 0x4
43 #define MEM_F_ALL 0x8
44 #define MEM_F_NO_MULTI 0x10
45 #define MEM_F_NO_RESCUE 0x20
46 #define MEM_F_REF_HDR 0x100
47 #define MEM_F_SOFTCLIP 0x200
48 #define MEM_F_SMARTPE 0x400
49 #define MEM_F_PRIMARY5 0x800
50 #define MEM_F_KEEP_SUPP_MAPQ 0x1000
51 #define MEM_F_XB 0x2000
52
53 typedef struct {
54 int a, b; // match score and mismatch penalty
55 int o_del, e_del;
56 int o_ins, e_ins;
57 int pen_unpaired; // phred-scaled penalty for unpaired reads
58 int pen_clip5,pen_clip3;// clipping penalty. This score is not deducted from the DP score.
59 int w; // band width
60 int zdrop; // Z-dropoff
61
62 uint64_t max_mem_intv;
63
64 int T; // output score threshold; only affecting output
65 int flag; // see MEM_F_* macros
66 int min_seed_len; // minimum seed length
67 int min_chain_weight;
68 int max_chain_extend;
69 float split_factor; // split into a seed if MEM is longer than min_seed_len*split_factor
70 int split_width; // split into a seed if its occurrence is smaller than this value
71 int max_occ; // skip a seed if its occurrence is larger than this value
72 int max_chain_gap; // do not chain seed if it is max_chain_gap-bp away from the closest seed
73 int n_threads; // number of threads
74 int chunk_size; // process chunk_size-bp sequences in a batch
75 float mask_level; // regard a hit as redundant if the overlap with another better hit is over mask_level times the min length of the two hits
76 float drop_ratio; // drop a chain if its seed coverage is below drop_ratio times the seed coverage of a better chain overlapping with the small chain
77 float XA_drop_ratio; // when counting hits for the XA tag, ignore alignments with score < XA_drop_ratio * max_score; only effective for the XA tag
78 float mask_level_redun;
79 float mapQ_coef_len;
80 int mapQ_coef_fac;
81 int max_ins; // when estimating insert size distribution, skip pairs with insert longer than this value
82 int max_matesw; // perform maximally max_matesw rounds of mate-SW for each end
83 int max_XA_hits, max_XA_hits_alt; // if there are max_hits or fewer, output them all
84 int8_t mat[25]; // scoring matrix; mat[0] == 0 if unset
85 } mem_opt_t;
86
87 typedef struct {
88 int64_t rb, re; // [rb,re): reference sequence in the alignment
89 int qb, qe; // [qb,qe): query sequence in the alignment
90 int rid; // reference seq ID
91 int score; // best local SW score
92 int truesc; // actual score corresponding to the aligned region; possibly smaller than $score
93 int sub; // 2nd best SW score
94 int alt_sc;
95 int csub; // SW score of a tandem hit
96 int sub_n; // approximate number of suboptimal hits
97 int w; // actual band width used in extension
98 int seedcov; // length of regions coverged by seeds
99 int secondary; // index of the parent hit shadowing the current hit; <0 if primary
100 int secondary_all;
101 int seedlen0; // length of the starting seed
102 int n_comp:30, is_alt:2; // number of sub-alignments chained together
103 float frac_rep;
104 uint64_t hash;
105 } mem_alnreg_t;
106
107 typedef struct { size_t n, m; mem_alnreg_t *a; } mem_alnreg_v;
108
109 typedef struct {
110 int low, high; // lower and upper bounds within which a read pair is considered to be properly paired
111 int failed; // non-zero if the orientation is not supported by sufficient data
112 double avg, std; // mean and stddev of the insert size distribution
113 } mem_pestat_t;
114
115 typedef struct { // This struct is only used for the convenience of API.
116 int64_t pos; // forward strand 5'-end mapping position
117 int rid; // reference sequence index in bntseq_t; <0 for unmapped
118 int flag; // extra flag
119 uint32_t is_rev:1, is_alt:1, mapq:8, NM:22; // is_rev: whether on the reverse strand; mapq: mapping quality; NM: edit distance
120 int n_cigar; // number of CIGAR operations
121 uint32_t *cigar; // CIGAR in the BAM encoding: opLen<<4|op; op to integer mapping: MIDSH=>01234
122 char *XA; // alternative mappings
123
124 int score, sub, alt_sc;
125 } mem_aln_t;
126
127 #ifdef __cplusplus
128 extern "C" {
129 #endif
130
131 smem_i *smem_itr_init(const bwt_t *bwt);
132 void smem_itr_destroy(smem_i *itr);
133 void smem_set_query(smem_i *itr, int len, const uint8_t *query);
134 void smem_config(smem_i *itr, int min_intv, int max_len, uint64_t max_intv);
135 const bwtintv_v *smem_next(smem_i *itr);
136
137 mem_opt_t *mem_opt_init(void);
138 void mem_fill_scmat(int a, int b, int8_t mat[25]);
139
140 extern void (*mem_fmt_fnc)(const mem_opt_t*, const bntseq_t*, kstring_t*, bseq1_t*, int, const mem_aln_t*, int, const mem_aln_t*, const mem_aln_t*);
141
142 /**
143 * Align a batch of sequences and generate the alignments in the SAM format
144 *
145 * This routine requires $seqs[i].{l_seq,seq,name} and write $seqs[i].sam.
146 * Note that $seqs[i].sam may consist of several SAM lines if the
147 * corresponding sequence has multiple primary hits.
148 *
149 * In the paired-end mode (i.e. MEM_F_PE is set in $opt->flag), query
150 * sequences must be interleaved: $n must be an even number and the 2i-th
151 * sequence and the (2i+1)-th sequence constitute a read pair. In this
152 * mode, there should be enough (typically >50) unique pairs for the
153 * routine to infer the orientation and insert size.
154 *
155 * @param opt alignment parameters
156 * @param bwt FM-index of the reference sequence
157 * @param bns Information of the reference
158 * @param pac 2-bit encoded reference
159 * @param n number of query sequences
160 * @param seqs query sequences; $seqs[i].seq/sam to be modified after the call
161 * @param pes0 insert-size info; if NULL, infer from data; if not NULL, it should be an array with 4 elements,
162 * corresponding to each FF, FR, RF and RR orientation. See mem_pestat() for more info.
163 */
164 void mem_process_seqs(const mem_opt_t *opt, const bwt_t *bwt, const bntseq_t *bns, const uint8_t *pac, int64_t n_processed, int n, bseq1_t *seqs, const mem_pestat_t *pes0);
165
166 /**
167 * Find the aligned regions for one query sequence
168 *
169 * Note that this routine does not generate CIGAR. CIGAR should be
170 * generated later by mem_reg2aln() below.
171 *
172 * @param opt alignment parameters
173 * @param bwt FM-index of the reference sequence
174 * @param bns Information of the reference
175 * @param pac 2-bit encoded reference
176 * @param l_seq length of query sequence
177 * @param seq query sequence
178 *
179 * @return list of aligned regions.
180 */
181 mem_alnreg_v mem_align1(const mem_opt_t *opt, const bwt_t *bwt, const bntseq_t *bns, const uint8_t *pac, int l_seq, const char *seq);
182
183 /**
184 * Generate CIGAR and forward-strand position from alignment region
185 *
186 * @param opt alignment parameters
187 * @param bns Information of the reference
188 * @param pac 2-bit encoded reference
189 * @param l_seq length of query sequence
190 * @param seq query sequence
191 * @param ar one alignment region
192 *
193 * @return CIGAR, strand, mapping quality and forward-strand position
194 */
195 mem_aln_t mem_reg2aln(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, int l_seq, const char *seq, const mem_alnreg_t *ar);
196 mem_aln_t mem_reg2aln2(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, int l_seq, const char *seq, const mem_alnreg_t *ar, const char *name);
197
198 /**
199 * Infer the insert size distribution from interleaved alignment regions
200 *
201 * This function can be called after mem_align1(), as long as paired-end
202 * reads are properly interleaved.
203 *
204 * @param opt alignment parameters
205 * @param l_pac length of concatenated reference sequence
206 * @param n number of query sequences; must be an even number
207 * @param regs region array of size $n; 2i-th and (2i+1)-th elements constitute a pair
208 * @param pes inferred insert size distribution (output)
209 */
210 void mem_pestat(const mem_opt_t *opt, int64_t l_pac, int n, const mem_alnreg_v *regs, mem_pestat_t pes[4]);
211
212 #ifdef __cplusplus
213 }
214 #endif
215
216 #endif