blib/lib/Bio/Cigar.pm

filter: Statementstmt 99.2% 124 / 125 Branchbran 91.3% 53 / 58 Conditioncond 82.6% 19 / 23 MC/DCmcdc 64.2% 9 / 14 Subroutinesub 100% 19 / 19 Podpod 85.7% 6 / 7 totaltotal 93.5% 230 / 246 CC 42 SCAR 25.3
CC
42
Cov
95%
_map_position
24.4
align
11.0
__ANON__
3.0
CRAP 12.6
↑ Summary
1 package Bio::Cigar;
2  
3 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 2 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
5 2 ▶use 5.014;
Subroutine BEGIN: called CC=1 SCAR=0.0
6  
7 =encoding utf-8
8  
9 =head1 NAME
10  
11 Bio::Cigar - Parse CIGAR strings and translate coordinates to/from reference/query
12  
13 =head1 SYNOPSIS
14  
15 use 5.014;
16 use Bio::Cigar;
17 my $cigar = Bio::Cigar->new("2M1D1M1I4M");
18 say "Query length is ", $cigar->query_length;
19 say "Reference length is ", $cigar->reference_length;
20  
21 my ($qpos, $op) = $cigar->rpos_to_qpos(3);
22 say "Alignment operation at reference position 3 is $op";
23  
24 my $query = "GCAAATGC";
25 my $ref = "AAAAGCAAATGC";
26 my $aln = $cigar->align($query, $ref, 5); # align query to pos 5 of ref
27 say foreach @$aln;
28  
29 =head1 DESCRIPTION
30  
31 Bio::Cigar is a small library to parse CIGAR strings ("Compact Idiosyncratic
32 Gapped Alignment Report"), such as those used in the SAM file format. CIGAR
33 strings are a run-length encoding which minimally describes the alignment of a
34 query sequence to an (often longer) reference sequence.
35  
36 Parsing follows the L<SAM v1 spec|http://samtools.github.io/hts-specs/SAMv1.pdf>
37 for the C<CIGAR> column.
38  
39 Parsed strings are represented by an object that provides a few utility
40 methods.
41  
42 =head1 ATTRIBUTES
43  
44 All attributes are read-only.
45  
46 =head2 string
47  
48 The CIGAR string for this object.
49  
50 =head2 reference_length
51  
52 The length of the reference sequence segment aligned with the query sequence
53 described by the CIGAR string.
54  
55 =head2 query_length
56  
57 The length of the query sequence described by the CIGAR string.
58  
59 =head2 ops
60  
61 An arrayref of C<[length, operation]> tuples describing the CIGAR string.
62 Lengths are integers, L<possible operations are below|/"CIGAR operations">.
63  
64 =cut
65  
66 2 our $VERSION = '1.02';
67  
68 2 ▶use Moo;
Subroutine BEGIN: called CC=1 SCAR=0.0
69 2 ▶use Types::Standard qw< ArrayRef Tuple Int Enum StrMatch >;
Subroutine BEGIN: called CC=1 SCAR=0.0
70 2 ▶use List::Util qw< sum >;
Subroutine BEGIN: called CC=1 SCAR=0.0
71 2 ▶use Carp qw< croak >;
Subroutine BEGIN: called CC=1 SCAR=0.0
72 2 ▶use namespace::clean;
Subroutine BEGIN: called CC=1 SCAR=0.0
73  
74 =head3 CIGAR operations
75  
76 The CIGAR operations are given in the following table, taken from the SAM v1
77 spec:
78  
79 Op Description
80 ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
81 M alignment match (can be a sequence match or mismatch)
82 I insertion to the reference
83 D deletion from the reference
84 N skipped region from the reference
85 S soft clipping (clipped sequences present in SEQ)
86 H hard clipping (clipped sequences NOT present in SEQ)
87 P padding (silent deletion from padded reference)
88 = sequence match
89 X sequence mismatch
90  
91 • H can only be present as the first and/or last operation.
92 • S may only have H operations between them and the ends of the string.
93 • For mRNA-to-genome alignment, an N operation represents an intron.
94 For other types of alignments, the interpretation of N is not defined.
95 • Sum of the lengths of the M/I/S/=/X operations shall equal the length of SEQ.
96  
97 =cut
98  
99 2 our $CIGAR_REGEX = qr/^
100 (\d*H)?(\d*S)?
101 (?<OP>\d*[MIDNP=X])*
102 (\d*S)?(\d*H)?
103 $/xa;
104  
105 2 has 'string',
106 is => 'ro',
107 isa => StrMatch[ $CIGAR_REGEX ],
108 required => 1;
109  
110 has 'query_length',
111 lazy => 1,
112 is => 'ro',
113 isa => Int,
114 4 ▶ default => sub { sum(map { $_ || 1 } $_[0]->string =~ /(\d*)[MIS=X]/ga) || 0 };
Subroutine __ANON__: called CC=3 SCAR=11.1
Branch: 1 branch
BranchTrueFalseTotal
&sum(map({$_ or 1;} $_[0]->string =~ /(\d*)[MIS=X]/ag)) or 0 4 0 4
Condition100%2/2
$_ || 1
l!l
131
MC/DC100%1/1
$_ || 1
$_
Truth table100%2/2
A
A= $_
Aresult
11
00
115  
116 has 'reference_length',
117 lazy => 1,
118 is => 'ro',
119 isa => Int,
120 3 ▶ default => sub { sum(map { $_ || 1 } $_[0]->string =~ /(\d*)[MDN=X]/ga) || 0 };
Subroutine __ANON__: called CC=3 SCAR=11.1
Branch: 1 branch
BranchTrueFalseTotal
&sum(map({$_ or 1;} $_[0]->string =~ /(\d*)[MDN=X]/ag)) or 0 3 0 3
Condition100%2/2
$_ || 1
l!l
71
MC/DC100%1/1
$_ || 1
$_
Truth table100%2/2
A
A= $_
Aresult
11
00
121  
122 2 has 'ops',
123 lazy => 1,
124 is => 'ro',
125 isa => ArrayRef[ Tuple[ Int, Enum[split '', 'MIDNSHP=X'] ] ],
126 builder => '_parse';
127  
128 16 ▶sub BUILDARGS {
Subroutine BUILDARGS: called CC=3 SCAR=11.0
Pod undocumented
129 16 my $class = shift;
130 16 ▶ if (@_ == 1 and not ref $_[0]) {
Branch: 1 branch
BranchTrueFalseTotal
if (@_ == 1 and not ref $_[0]) { } 15 1 16
Condition66%2/3
@_ == 1 and not ref $_[0]
!ll&&!rl&&r
1015
MC/DC50%1/2
@_ == 1 and not ref $_[0]
@_ == 1 not ref $_[0]
Truth table66%2/3
A and not(B)
A= @_ == 1B= not ref $_[0]
ABresult
0X0
100
111
131 15 return { string => $_[0] };
132 } else {
133 1 croak sprintf "%s->new must be called with a string as the sole argument", __PACKAGE__;
134 }
135 }
136  
137 5 ▶sub _parse {
Subroutine _parse: called CC=3 SCAR=11.0
138 5 my $self = shift;
139 5 my $cigar = $self->string;
140 5 my @ops;
141 5 for my $op (grep defined, $cigar =~ /(\d*[MIDNSHP=X])/g) {
142 26 my ($len, $type) = $op =~ /(\d*)(\D*)/a;
143 26 ▶ push @ops, [ $len || 1, uc $type ];
Condition100%2/2
$len || 1
l!l
242
MC/DC100%1/1
$len || 1
$len
Truth table100%2/2
A
A= $len
Aresult
11
00
144 }
145 5 return \@ops;
146 }
147  
148 =head1 CONSTRUCTOR
149  
150 =head2 new
151  
152 Takes a CIGAR string as the sole argument and returns a new Bio::Cigar object.
153  
154 =head1 METHODS
155  
156 =head2 rpos_to_qpos
157  
158 Takes a reference position (origin 1, base-numbered) and returns the
159 corresponding position (origin 1, base-numbered) on the query sequence. Indels
160 affect how the numbering maps from reference to query.
161  
162 In list context returns a tuple of C<[query position, operation at position]>.
163 Operation is a single-character string. See the
164 L<table of CIGAR operations|/"CIGAR operations">.
165  
166 If the reference position does not map to the query sequence (as with a
167 deletion, for example), returns C<undef> or C<[undef, operation]>.
168  
169 =head2 qpos_to_rpos
170  
171 Takes a query position (origin 1, base-numbered) and returns the corresponding
172 position (origin 1, base-numbered) on the reference sequence. Indels affect
173 how the numbering maps from query to reference.
174  
175 In list context returns a tuple of C<[references position, operation at position]>.
176 Operation is a single-character string. See the
177 L<table of CIGAR operations|/"CIGAR operations">.
178  
179 If the query position does not map to the reference sequence (as with an
180 insertion, for example), returns C<undef> or C<[undef, operation]>.
181  
182 =head2 op_at_rpos
183  
184 Takes a reference position and returns the operation at that position. Simply
185 a shortcut for calling L</rpos_to_qpos> in list context and discarding the
186 first return value.
187  
188 =head2 op_at_qpos
189  
190 Takes a query position and returns the operation at that position. Simply
191 a shortcut for calling L</qpos_to_rpos> in list context and discarding the
192 first return value.
193  
194 =head2 reversed
195  
196 Returns a new Bio::Cigar object with a CIGAR string that's the reverse of this
197 one, i.e. the last operation becomes the first, the second-to-last the second,
198 etc. until the first operation becomes the last.
199  
200 =head2 align($query, $reference, $start_pos=1, $reversed=0)
201  
202 Takes a query sequence and a reference sequence and aligns them according to
203 the CIGAR string, using gap characters (C<->) for indels and spaces for soft
204 clipping. This is pure string manipulation and as such the match and mismatch
205 operators (C<=> and C<X>) are assumed to be correct for the given input
206 sequences and not verified. Returns an array ref of C<[query seq, ref seq]>.
207  
208 Optionally, the leftmost reference position (origin 1) can be passed, i.e. the
209 query is aligned starting at that position.
210  
211 When C<$reversed> is given a true value, the reverse complement of the passed
212 query sequence is used to generate the alignment. B<Only the IUPAC nucleotide
213 codes C<ATCGU> are currently supported for reverse complementation.>
214  
215 =cut
216  
217 # Consumption table based on
218 # https://github.com/samtools/htslib/blob/develop/htslib/sam.h#L81-L100
219 2 my %op_consumes = (
220 # op => [query, reference]
221 'M' => [1, 1],
222 'I' => [1, 0],
223 'D' => [0, 1],
224 'N' => [0, 1],
225 'S' => [1, 0],
226 'H' => [0, 0],
227 'P' => [0, 0],
228 '=' => [1, 1],
229 'X' => [1, 1],
230 );
231  
232 38 ▶sub rpos_to_qpos {
Subroutine rpos_to_qpos: called CC=1 SCAR=0.0
Pod documented
233 38 my $self = shift;
234 38 return $self->_map_position( rpos => @_ );
235 }
236  
237 39 ▶sub qpos_to_rpos {
Subroutine qpos_to_rpos: called CC=1 SCAR=0.0
Pod documented
238 39 my $self = shift;
239 39 return $self->_map_position( qpos => @_ );
240 }
241  
242 77 ▶sub _map_position {
Subroutine _map_position: called CC=24 SCAR=31.9
243 77 my $self = shift;
244 77 my $from = shift;
245 77 my $target = shift;
246 77 ▶ my $target_len = $from eq "rpos" ? "reference_length" : "query_length";
Branch: 1 branch
BranchTrueFalseTotal
$from eq 'rpos' ? : 38 39 77
247  
248 77 my $rpos = 0;
249 77 my $qpos = 0;
250  
251 77 ▶ croak sprintf "$from = %d is < 1 or > $target_len (%d)", $target, $self->$target_len
Branch: 1 branch
BranchTrueFalseTotal
if $target < 1 or $target > $self->$target_len 5 72 77
Condition100%3/3
$target < 1 or $target > $self->$target_len
l!l&&r!l&&!r
2372
MC/DC100%2/2
$target < 1 or $target > $self->$target_len
$target < 1 $target > $self->$target_len
Truth table100%3/3
A or B
A= $target < 1B= $target > $self->$target_len
ABresult
1X1
011
000
252 if $target < 1 or $target > $self->$target_len;
253  
254 # Each cigar operation consumes the reference, query, or both. We keep
255 # track of both positions until the query/reference position hits the
256 # target. Then we return the equivalent other position.
257  
258 72 for my $op (@{ $self->ops }) {
259 222 my ($len, $type) = @$op;
260 222 my $consumes = $op_consumes{$type};
261 222 ▶ next unless $consumes->[0] or $consumes->[1];
Branch: 1 branch
BranchTrueFalseTotal
unless $consumes->[0] or $consumes->[1] 0 222 222
Condition66%2/3
$consumes->[0] or $consumes->[1]
l!l&&r!l&&!r
195270
MC/DC0%0/2
$consumes->[0] or $consumes->[1]
$consumes->[0] $consumes->[1]
Truth table66%2/3
A or B
A= $consumes->[0]B= $consumes->[1]
ABresult
1X1
011
000
262  
263 222 ▶ $qpos += $len if $consumes->[0];
Branch: 1 branch
BranchTrueFalseTotal
if $consumes->[0] 195 27 222
264 222 ▶ $rpos += $len if $consumes->[1];
Branch: 1 branch
BranchTrueFalseTotal
if $consumes->[1] 150 72 222
265  
266 # The logic could be written with more variables to reduce the
267 # duplication in this if/else, but I think the clarity of the logic is
268 # enhanced by the similarity of the if/else branches. Adding more
269 # varibles to make the logic generic muddies the simplicity.
270 222 ▶ if ($from eq "rpos") {
Branch: 1 branch
BranchTrueFalseTotal
if ($from eq 'rpos') { } 114 108 222
271 114 ▶ if ($rpos > $target) {
Branch: 1 branch
BranchTrueFalseTotal
if ($rpos > $target) 21 93 114
272 21 my $overshoot = $rpos - $target;
273 21 $rpos -= $overshoot;
274 21 $qpos -= $overshoot;
275 }
276 114 ▶ if ($rpos == $target) {
Branch: 1 branch
BranchTrueFalseTotal
if ($rpos == $target) 36 78 114
277 36 ▶ if ($consumes->[1] and not $consumes->[0]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($consumes->[1] and not $consumes->[0]) { } 3 33 36
Condition66%2/3
$consumes->[1] and not $consumes->[0]
!ll&&!rl&&r
0333
MC/DC50%1/2
$consumes->[1] and not $consumes->[0]
$consumes->[1] not $consumes->[0]
Truth table66%2/3
A and not(B)
A= $consumes->[1]B= not $consumes->[0]
ABresult
0X0
100
111
278 # Reference positions which are missing in the query sequence
279 # don't have a corresponding query position.
280 3 ▶ return wantarray ? (undef, $type) : undef;
Branch: 1 branch
BranchTrueFalseTotal
wantarray ? : 2 1 3
281 } else {
282 33 ▶ $qpos <= $self->query_length
Branch: 1 branch
BranchTrueFalseTotal
$qpos <= $self->query_length or croak(sprintf("Bug! Assertion failed: qpos <= qlen (target = %d, rpos = %d, qpos = %d, qlen = %d, cigar = %s)", $target, $rpos, $qpos, $self->query_length, $self->string)) 33 0 33
283 or croak sprintf "Bug! Assertion failed: qpos <= qlen"
284 . " (target = %d, rpos = %d, qpos = %d, qlen = %d, cigar = %s)",
285 $target, $rpos, $qpos, $self->query_length, $self->string;
286 33 ▶ return wantarray ? ($qpos, $type) : $qpos;
Branch: 1 branch
BranchTrueFalseTotal
wantarray ? : 22 11 33
287 }
288 }
289 } else {
290 108 ▶ if ($qpos > $target) {
Branch: 1 branch
BranchTrueFalseTotal
if ($qpos > $target) 18 90 108
291 18 my $overshoot = $qpos - $target;
292 18 $rpos -= $overshoot;
293 18 $qpos -= $overshoot;
294 }
295 108 ▶ if ($qpos == $target) {
Branch: 1 branch
BranchTrueFalseTotal
if ($qpos == $target) 36 72 108
296 36 ▶ if ($consumes->[0] and not $consumes->[1]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($consumes->[0] and not $consumes->[1]) { } 12 24 36
Condition66%2/3
$consumes->[0] and not $consumes->[1]
!ll&&!rl&&r
02412
MC/DC50%1/2
$consumes->[0] and not $consumes->[1]
$consumes->[0] not $consumes->[1]
Truth table66%2/3
A and not(B)
A= $consumes->[0]B= not $consumes->[1]
ABresult
0X0
100
111
297 # Query positions which are insertions in the reference sequence
298 # don't have a corresponding reference position.
299 12 ▶ return wantarray ? (undef, $type) : undef;
Branch: 1 branch
BranchTrueFalseTotal
wantarray ? : 8 4 12
300 } else {
301 24 ▶ $rpos <= $self->reference_length
Branch: 1 branch
BranchTrueFalseTotal
$rpos <= $self->reference_length or croak(sprintf("Bug! Assertion failed: rpos <= rlen (target = %d, qpos = %d, rpos = %d, rlen = %d, cigar = %s)", $target, $qpos, $rpos, $self->reference_length, $self->string)) 24 0 24
302 or croak sprintf "Bug! Assertion failed: rpos <= rlen"
303 . " (target = %d, qpos = %d, rpos = %d, rlen = %d, cigar = %s)",
304 $target, $qpos, $rpos, $self->reference_length, $self->string;
305 24 ▶ return wantarray ? ($rpos, $type) : $rpos;
Branch: 1 branch
BranchTrueFalseTotal
wantarray ? : 16 8 24
306 }
307 }
308 }
309 }
310 0 croak sprintf "Bug! Ran out of ops but couldn't map %s %d"
311 . " (rpos = %d, qpos = %d, cigar = %s)",
312 $from, $target, $rpos, $qpos, $self->string;
313 }
314  
315 12 ▶sub op_at_rpos {
Subroutine op_at_rpos: called CC=1 SCAR=0.0
Pod documented
316 12 my $self = shift;
317 12 my ($qpos, $type) = $self->rpos_to_qpos(@_);
318 12 return $type;
319 }
320  
321 12 ▶sub op_at_qpos {
Subroutine op_at_qpos: called CC=1 SCAR=0.0
Pod documented
322 12 my $self = shift;
323 12 my ($rpos, $type) = $self->qpos_to_rpos(@_);
324 12 return $type;
325 }
326  
327 1 ▶sub reversed {
Subroutine reversed: called CC=1 SCAR=0.0
Pod documented
328 1 my $self = shift;
329 1 return Bio::Cigar->new(join "", map { join "", @$_ } reverse @{$self->ops});
330 }
331  
332 6 ▶sub align {
Subroutine align: called CC=11 SCAR=24.0
Pod documented
333 6 my ($self, $query, $ref, $ref_start, $reversed) = @_;
334 6 ▶ $ref_start //= 1; # default to first posiiton
Condition100%2/2
$ref_start //= 1
l!l
42
MC/DC100%1/1
$ref_start //= 1
$ref_start
Truth table100%2/2
A
A= $ref_start
Aresult
11
00
335  
336 ### Sanity checks
337 # Note: The match/mismatch operators (=/X) are currently not verified to
338 # be correct for the given input sequences.
339 #
340 # Note: The reference length will likely not match because it is often
341 # longer than the query and the CIGAR string doesn't account for that. The
342 # best matching thing would be N, but it seems to be mainly used for
343 # introns.
344  
345 # Reference start position
346 6 ▶ croak "Reference start position must be positive, but $ref_start given"
Branch: 1 branch
BranchTrueFalseTotal
unless $ref_start > 0 1 5 6
347 unless $ref_start > 0;
348  
349 # Query length
350 5 my $query_len = $self->query_length;
351 5 ▶ croak "Query was expected to have length $query_len, but has length ",
Branch: 1 branch
BranchTrueFalseTotal
unless $query_len == length $query 1 4 5
352 length($query), " instead"
353 unless $query_len == length($query);
354  
355 ### Variables
356 4 my (@query_aln, @ref_aln); # stores chunks of aligned sequences
357 4 my ($query_pos, $ref_pos) = (0, 0); # current position in sequences
358  
359 ### Handle optional arguments.
360 # Handle reference start position.
361 4 $ref_pos += $ref_start - 1; # convert 1-based start to 0-based pos
362 4 push @query_aln, ' ' x $ref_pos; # start at correct position
363 4 push @ref_aln, substr $ref, 0, $ref_pos;
364  
365 # Handle reversed query matches.
366 4 ▶ if ($reversed) {
Branch: 1 branch
BranchTrueFalseTotal
if ($reversed) 1 3 4
367 1 $query = reverse $query =~ tr/ATGCU/TACGA/r; # reverse complement
368 }
369  
370 ### Iterate CIGAR ops and generate alignment chunks.
371 4 foreach my $op (@{$self->ops}) {
372 36 my ($op_len, $op_type) = @$op;
373 36 my ($consumes_query, $consumes_ref) = @{ $op_consumes{$op_type} };
374  
375 # Get next chunk of respective sequence and update position. Insert
376 # gaps in the other sequence if necessary.
377 36 ▶ if ($consumes_query) {
Branch: 1 branch
BranchTrueFalseTotal
if ($consumes_query) 20 16 36
378 20 push @query_aln, substr $query, $query_pos, $op_len;
379 20 $query_pos += $op_len;
380  
381 20 ▶ unless ($consumes_ref) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($consumes_ref) 8 12 20
382 # Use spaces for soft clips, and dashes for indels etc.
383 8 ▶ my $gap_char = $op_type eq 'S' ? ' ' : '-';
Branch: 1 branch
BranchTrueFalseTotal
$op_type eq 'S' ? : 4 4 8
384 8 push @ref_aln, $gap_char x $op_len;
385 }
386 }
387 36 ▶ if ($consumes_ref) {
Branch: 1 branch
BranchTrueFalseTotal
if ($consumes_ref) 20 16 36
388 20 push @ref_aln, substr $ref, $ref_pos, $op_len;
389 20 $ref_pos += $op_len;
390  
391 20 ▶ unless ($consumes_query) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($consumes_query) 8 12 20
392 8 push @query_aln, '-' x $op_len;
393 }
394 }
395 }
396  
397 # Join chunks and return aligned sequences.
398 4 my $query_aln = join '', @query_aln;
399 4 my $ref_aln = join '', @ref_aln;
400  
401 4 return [$query_aln, $ref_aln];
402 }
403  
404 =head1 AUTHOR
405  
406 Thomas Sibley E<lt>trsibley@uw.eduE<gt>
407  
408 Felix Kühnl E<lt>felix@bioinf.uni-leipzig.deE<gt>
409  
410 =head1 COPYRIGHT
411  
412 Copyright 2014- Mullins Lab, Department of Microbiology, University of Washington.
413  
414 =head1 LICENSE
415  
416 This library is free software; you can redistribute it and/or modify it under
417 the GNU General Public License, version 2.
418  
419 =head1 SEE ALSO
420  
421 L<SAMv1 spec|http://samtools.github.io/hts-specs/SAMv1.pdf>
422  
423 =cut
424  
425 2 1;
↑ Summary