Sequence Alignment/Map Format Specification

This is an unofficial HTML rendering of the specification. The official specification is maintained at samtools/hts-specs. This rendering is based on commit b5341fb, dated 12 Aug 2025.

SAM stands for Sequence Alignment/Map format. It is a TAB-delimited text format consisting of a header section, which is optional, and an alignment section. If present, the header must be prior to the alignments. Header lines start with ‘@’, while alignment lines do not. Each alignment line has 11 mandatory fields for essential alignment information such as mapping position, and variable number of optional fields for flexible or aligner specific information.

This specification is for version 1.6 of the SAM and BAM formats. Each SAM and BAM file may optionally specify the version being used via the @HD VN tag. For full version history see Appendix 7.

SAM file contents are 7-bit US-ASCII, except for certain field values as individually specified which may contain other Unicode characters encoded in UTF-8. Alternatively and equivalently, SAM files are encoded in UTF-8 but non-ASCII characters are permitted only within certain field values as explicitly specified in the descriptions of those fields. ¹

Where it makes a difference, SAM file contents should be read and written using the POSIX / C locale. For example, floating-point values in SAM always use ‘.’ for the decimal-point character.

The regular expressions in this specification are written using the POSIX / IEEE Std 1003.1 extended syntax.

1.1 An example#

Suppose we have the following alignment with bases in lowercase clipped from the alignment. Read r001/1 and r001/2 constitute a read pair; r003 is a chimeric read; r004 represents a split alignment.

Coor 12345678901234 5678901234567890123456789012345 ref AGCATGTTAGATAA**GATAGCTGTGCTAGTAGGCAGTCAGCGCCAT

+r001/1        TTAGATAAAGGATA*CTG
+r002         aaaAGATAA*GGATA
+r003       gcctaAGCTAA
+r004                     ATAGCT..............TCAGC
-r003                            ttagctTAGGC
-r001/2                                        CAGCGGCAT

The corresponding SAM format is:²

@HD VN:1.6 SO:coordinate @SQ SN:ref LN:45 r001 99 ref 7 30 8M2I4M1D3M = 37 39 TTAGATAAAGGATACTG * r002 0 ref 9 30 3S6M1P1I4M * 0 0 AAAAGATAAGGATA * r003 0 ref 9 30 5S6M * 0 0 GCCTAAGCTAA * SA:Z:ref,29,-,6H5M,17,0; r004 0 ref 16 30 6M14N5M * 0 0 ATAGCTTCAGC * r003 2064 ref 29 17 6H5M * 0 0 TAGGC * SA:Z:ref,9,+,5S6M,30,1; r001 147 ref 37 30 9M = 7 -39 CAGCGGCAT * NM:i:1

1.2 Terminologies and Concepts#

Template
A DNA/RNA sequence part of which is sequenced on a sequencing machine or assembled from raw sequences.

Segment
A contiguous sequence or subsequence.

Read
A raw sequence that comes off a sequencing machine. A read may consist of multiple segments. For sequencing data, reads are indexed by the order in which they are sequenced.

Linear alignment
An alignment of a read to a single reference sequence that may include insertions, deletions, skips and clipping, but may not include direction changes (i.e., one portion of the alignment on forward strand and another portion of alignment on reverse strand). A linear alignment can be represented in a single SAM record.

Chimeric alignment
An alignment of a read that cannot be represented as a linear alignment. A chimeric alignment is represented as a set of linear alignments that do not have large overlaps. Typically, one of the linear alignments in a chimeric alignment is considered the “representative” alignment, and the others are called “supplementary” and are distinguished by the supplementary alignment flag. All the SAM records in a chimeric alignment have the same QNAME and the same values for 0x40 and 0x80 flags (see Section 1.4). The decision regarding which linear alignment is representative is arbitrary.

Read alignment
A linear alignment or a chimeric alignment that is the complete representation of the alignment of the read.

Multiple mapping
The correct placement of a read may be ambiguous, e.g., due to repeats. In this case, there may be multiple read alignments for the same read. One of these alignments is considered primary. All the other alignments have the secondary alignment flag set in the SAM records that represent them. All the SAM records have the same QNAME and the same values for 0x40 and 0x80 flags. Typically the alignment designated primary is the best alignment, but the decision may be arbitrary.

1-based coordinate system
A coordinate system where the first base of a sequence is one. In this coordinate system, a region is specified by a closed interval. For example, the region between the 3rd and the 7th bases inclusive is $[3,7]$. The SAM, VCF, GFF and Wiggle formats are using the 1-based coordinate system.

0-based coordinate system
A coordinate system where the first base of a sequence is zero. In this coordinate system, a region is specified by a half-closed-half-open interval. For example, the region between the 3rd and the 7th bases inclusive is $[2,7)$. The BAM, BCFv2, BED, and PSL formats are using the 0-based coordinate system.

Phred scale
Given a probability $0<p\le 1$, the phred scale of $p$ equals $-10\log_{10}p$, rounded to the closest integer.

1.2.1 Character set restrictions#

Reference sequence names, CIGAR strings, and several other field types are used as values or parts of values of other fields in SAM and related formats such as VCF. To ensure that these other fields’ representations are unambiguous, these field types disallow particular delimiter characters.

Query or read names may contain any printable ASCII characters in the range [!-~] apart from ‘@’, so that SAM alignment lines can be easily distinguished from header lines. (They are also limited in length.)

Reference sequence names may contain any printable ASCII characters in the range [!-~] apart from backslashes, commas, quotation marks, and brackets—i.e., apart from ‘\ , "`' () [] {} <>’—and may not start with ” or ‘=’. ³

Thus they match the following regular expression:

For clarity, elsewhere in this specification we write this set of allowed characters as a character class [] and extend the POSIX regular expression notation to use = to indicate the omission of ” and ‘=’ from the character class. Thus this regular expression can be written more clearly as [=][]*.

1.3 The header section#

Each header line begins with the character ‘@’ followed by one of the two-letter header record type codes defined in this section. In the header, each line is TAB-delimited and, apart from @CO lines, each data field follows a format ‘TAG:VALUE’ where TAG is a two-character string that defines the format and content of VALUE. Thus header lines match /@(HD|SQ|RG|PG)(92t[A-Za-z][A-Za-z0-9]:[ -]+)+$/ or /@CO92t.*/. Within each (non-@CO) header line, no field tag may appear more than once and the order in which the fields appear is not significant.

The following table describes the header record types that may be used and their predefined tags. Tags listed with ’*’ are required; e.g., every @SQ header line must have SN and LN fields. As with alignment optional fields (see Section 1.5), you can freely add new tags for further data fields. Tags containing lowercase letters are reserved for local use and will not be formally defined in any future version of this specification. ⁴

1.3.1 Defined sub-sort terms#

While the SS sub-sort field allows implementation-defined keywords, some terms are predefined with specific meanings.

lexicographical
sort order is defined as a character-based dictionary sort with the character order as defined by the POSIX C locale. For example “abc”, “abc17”, “abc5”, “abc59” and “abcd” are in lexicographical order.

natural
sort order is similar to lexicographical order except that runs of adjacent digits are considered to be numbers embedded within the text string, ordered numerically when compared to each other and ordered as single digits when compared to the surrounding non-digit characters. Runs that differ only in the number of leading zeros (thus are numerically tied) are ordered by more-zeros coming before fewer-zeros. The characters ‘-’ and ‘.’ are considered as ordinary characters, so apparently negative or fractional values are not treated as part of an embedded number. For example, “abc”, “abc+5”, “abc-5”, “abc.d”, “abc03”, “abc5”, “abc008”, “abc08”, “abc8”, “abc17”, “abc17.+”, “abc17.2”, “abc17.d”, “abc59” and “abcd” are in natural order.

umi
is a lexicographical sort by the UMI tag. The MI tag should be used for comparing UMIs. The RX tag may be used in its absence but is not guaranteed to be unique across multiple libraries.

1.3.2 Reference MD5 calculation#

The M5 tag on @SQ lines allows reference sequences to be uniquely identified through the MD5 digest of the sequence itself. As the digest is based on the sequence and nothing else, it can help resolve ambiguities with reference naming. For example, it allows a quick way of checking that references named ‘1’, ‘Chr1’ and ‘chr1’ in different files are in fact the same.

The reference sequence must be in the 7-bit US-ASCII character set. All valid reference bases can be represented in this set, and it avoids the problem of determining exactly which 8-bit representation may have been used. Padding characters (See Section 3.2) must be represented only using the ’*’ character.

The digest is calculated as follows:

• All characters outside of the inclusive range 33 (”) to 126 (”) are stripped out. This removes all unprintable and whitespace characters including spaces and new lines. Everything else is retained, even if not a legal nucleotide code.

• All lowercase characters are converted to uppercase. This operation is equivalent to calling toupper() on characters in the POSIX locale.

• The MD5 digest is calculated as described in RFC 1321 and presented as a 32 character lowercase hexadecimal number.

As an example, if the reference contains the following characters (including spaces):

ACGT ACGT ACGT
acgt acgt acgt
... 12345 !!!

then the digest is that of the string ACGTACGTACGTACGTACGTACGT...12345!!! and the resulting tag would be M5:dfabdbb36e239a6da88957841f32b8e4.

In padded SAM files, the padding bases should be inserted into the reference as ’*’ characters. Taking the example in Section 3.2, the padded version of the reference is

AGCATGTTAGATAA**GATAGCTGTGCTAGTAGGCAGTCAGCGCCAT

and the corresponding tag is M5:caad65b937c4bc0b33c08f62a9fb5411.

1.4 The alignment section: mandatory fields#

In the SAM format, each alignment line typically represents the linear alignment of a segment. Each line consists of 11 or more TAB-separated fields. The first eleven fields are always present and in the order shown below; if the information represented by any of these fields is unavailable, that field’s value will be a placeholder, either ‘0’ or ” as determined by the field’s type. The following table gives an overview of these mandatory fields in the SAM format:

All mapped segments in alignment lines are represented on the forward genomic strand. For segments that have been mapped to the reverse strand, the recorded SEQ is reverse complemented from the original unmapped sequence and CIGAR, QUAL, and strand-sensitive optional fields are reversed and thus recorded consistently with the sequence bases as represented.

1. QNAME: Query template NAME. Reads/segments having identical QNAME are regarded to come from the same template. A QNAME ” indicates the information is unavailable. In a SAM file, a read may occupy multiple alignment lines, when its alignment is chimeric or when multiple mappings are given.

2. FLAG: Combination of bitwise FLAGs.⁵ Each bit is explained in the following table:

   Bit	Description
   1 0x1	template having multiple segments in sequencing
   2 0x2	each segment properly aligned according to the aligner
   4 0x4	segment unmapped
   8 0x8	next segment in the template unmapped
   16 0x10	SEQ being reverse complemented
   32 0x20	SEQ of the next segment in the template being reverse complemented
   64 0x40	the first segment in the template
   128 0x80	the last segment in the template
   256 0x100	secondary alignment
   512 0x200	not passing filters, such as platform/vendor quality controls
   1024 0x400	PCR or optical duplicate
   2048 0x800	supplementary alignment

   • For each read/contig in a SAM file, it is required that one and only one line associated with the read satisfies ‘FLAG & 0x900 == 0’. This line is called the primary line of the read.

   • Bit 0x100 marks the alignment not to be used in certain analyses when the tools in use are aware of this bit. It is typically used to flag alternative mappings when multiple mappings are presented in a SAM.

   • Bit 0x800 indicates that the corresponding alignment line is part of a chimeric alignment. A line flagged with 0x800 is called as a supplementary line.

   • Bit 0x4 is the only reliable place to tell whether the read is unmapped. If 0x4 is set, no assumptions can be made about RNAME, POS, CIGAR, MAPQ, and bits 0x2, 0x100, and 0x800.

   • Bit 0x10 indicates whether SEQ has been reverse complemented and QUAL reversed. When bit 0x4 is unset, this corresponds to the strand to which the segment has been mapped: bit 0x10 unset indicates the forward strand, while set indicates the reverse strand. When 0x4 is set, this indicates whether the unmapped read is stored in its original orientation as it came off the sequencing machine.

   • Bits 0x40 and 0x80 reflect the read ordering within each template inherent in the sequencing technology used.⁶ If 0x40 and 0x80 are both set, the read is part of a linear template, but it is neither the first nor the last read. If both 0x40 and 0x80 are unset, the index of the read in the template is unknown. This may happen for a non-linear template or when this information is lost during data processing.

   • If 0x1 is unset, no assumptions can be made about 0x2, 0x8, 0x20, 0x40 and 0x80.

   • Bits that are not listed in the table are reserved for future use. They should not be set when writing and should be ignored on reading by current software.

3. RNAME: Reference sequence NAME of the alignment. If @SQ header lines are present, RNAME (if not ’*’) must be present in one of the SQ-SN tag. An unmapped segment without coordinate has a ’*’ at this field. However, an unmapped segment may also have an ordinary coordinate such that it can be placed at a desired position after sorting. If RNAME is ’*’, no assumptions can be made about POS and CIGAR.

4. POS: 1-based leftmost mapping POSition of the first CIGAR operation that “consumes” a reference base (see table below). The first base in a reference sequence has coordinate 1. POS is set as 0 for an unmapped read without coordinate. If POS is 0, no assumptions can be made about RNAME and CIGAR.

5. MAPQ: MAPping Quality. It equals $-10\log_{10}\Pr\{\textit{mapping \textit{position} is \textit{wrong}}\}$, rounded to the nearest integer. A value 255 indicates that the mapping quality is not available.

6. CIGAR: CIGAR string. The CIGAR operations are given in the following table (set ’*’ if unavailable):

   Op	BAM	Description	Consumes query	Consumes reference
   M	0	alignment match (can be a sequence match or mismatch)	yes	yes
   I	1	insertion to the reference	yes	no
   D	2	deletion from the reference	no	yes
   N	3	skipped region from the reference	no	yes
   S	4	soft clipping (clipped sequences present in SEQ)	yes	no
   H	5	hard clipping (clipped sequences NOT present in SEQ)	no	no
   P	6	padding (silent deletion from padded reference)	no	no
   =	7	sequence match	yes	yes
   X	8	sequence mismatch	yes	yes

   • “Consumes query” and “consumes reference” indicate whether the CIGAR operation causes the alignment to step along the query sequence and the reference sequence respectively.

   • H can only be present as the first and/or last operation.

   • S may only have H operations between them and the ends of the CIGAR string.

   • For mRNA-to-genome alignment, an N operation represents an intron. For other types of alignments, the interpretation of N is not defined.

   • Sum of lengths of the operations shall equal the length of SEQ.

7. RNEXT: Reference sequence name of the primary alignment of the NEXT read in the template. For the last read, the next read is the first read in the template. If @SQ header lines are present, RNEXT (if not ’*’ or ’=’) must be present in one of the SQ-SN tag. This field is set as ’*’ when the information is unavailable, and set as ’=’ if RNEXT is identical RNAME. If not ’=’ and the next read in the template has one primary mapping (see also bit 0x100 in FLAG), this field is identical to RNAME at the primary line of the next read. If RNEXT is ’*’, no assumptions can be made on PNEXT and bit 0x20.

8. PNEXT: 1-based Position of the primary alignment of the NEXT read in the template. Set as 0 when the information is unavailable. This field equals POS at the primary line of the next read. If PNEXT is 0, no assumptions can be made on RNEXT and bit 0x20.

9. TLEN: signed observed Template LENgth. For primary reads where the primary alignments of all reads in the template are mapped to the same reference sequence, the absolute value of TLEN equals the distance between the mapped end of the template and the mapped start of the template, inclusively (i.e., $\textit{end}-\textit{start}+1$). ⁷ Note that mapped base is defined to be one that aligns to the reference as described by CIGAR, hence excludes soft-clipped bases. The TLEN field is positive for the leftmost segment of the template, negative for the rightmost, and the sign for any middle segment is undefined. If segments cover the same coordinates then the choice of which is leftmost and rightmost is arbitrary, but the two ends must still have differing signs. It is set as 0 for a single-segment template or when the information is unavailable (e.g., when the first or last segment of a multi-segment template is unmapped or when the two are mapped to different reference sequences).

   The intention of this field is to indicate where the other end of the template has been aligned without needing to read the remainder of the SAM file. Unfortunately there has been no clear consensus on the definitions of the template mapped start and end. Thus the exact definitions are implementation-defined. ⁸

10. SEQ: segment SEQuence. This field can be a ’*’ when the sequence is not stored. If not a ’*’, the length of the sequence must equal the sum of lengths of operations in CIGAR. An ’=’ denotes the base is identical to the reference base. No assumptions can be made on the letter cases.

11. QUAL: ASCII of base QUALity plus 33 (same as the quality string in the Sanger FASTQ format). A base quality is the phred-scaled base error probability which equals $-10\log_{10}\Pr\{\textit{base is \textit{wrong}}\}$. This field can be a ’*’ when quality is not stored.⁹ If not a ’*’, SEQ must not be a ’*’ and the length of the quality string ought to equal the length of SEQ.

1.5 The alignment section: optional fields#

All optional fields follow the TAG:TYPE:VALUE format where TAG is a two-character string that matches /[A-Za-z][A-Za-z0-9]/. Within each alignment line, no TAG may appear more than once and the order in which the optional fields appear is not significant. A TAG containing lowercase letters is reserved for end users. In an optional field, TYPE is a single case-sensitive letter which defines the format of VALUE:

For an integer or numeric array (type ‘B’), the first letter indicates the type of numbers in the following comma separated array. The letter can be one of ‘cCsSiIf’, corresponding to int8_t (signed 8-bit integer), uint8_t (unsigned 8-bit integer), int16_t, uint16_t, int32_t, uint32_t and float, respectively. During import/export, the element type may be changed if the new type is also compatible with the array.

Predefined tags are described in the separate Sequence Alignment/Map Optional Fields Specification.¹⁰ See that document for details of existing standard tag fields and conventions around creating new tags that may be of general interest. Tags starting with ‘X’, ‘Y’ or ‘Z’ and tags containing lowercase letters in either position are reserved for local use and will not be formally defined in any future version of these specifications.

2 Recommended Practice for the SAM Format#

This section describes the best practice for representing data in the SAM format. They are not required in general, but may be required by a specific software package for it to function properly.

1. The header section

   1. The @HD line should be present, with either the SO tag or the GO tag (but not both) specified.

   2. The @SQ lines should be present if reads have been mapped.

   3. When a RG tag appears anywhere in the alignment section, there should be a single corresponding @RG line with matching ID tag in the header.

   4. When a PG tag appears anywhere in the alignment section, there should be a single corresponding @PG line with matching ID tag in the header.

2. Adjacent CIGAR operations should be different.

3. No alignments should be assigned mapping quality 255.

4. Unmapped reads

   1. For a unmapped paired-end or mate-pair read whose mate is mapped, the unmapped read should have RNAME and POS identical to its mate.

   2. If all segments in a template are unmapped, their RNAME should be set as ’*’ and POS as 0.

   3. If POS plus the sum of lengths of operations in CIGAR exceeds the length specified in the LN field of the @SQ header line (if exists) with an SN equal to RNAME, the alignment should be unmapped, unless the reference sequence is circular (see below).

   4. Unmapped reads should be stored in the orientation in which they came off the sequencing machine and have their reverse flag bit (0x10) correspondingly unset.

5. Multiple mapping

   1. When one segment is present in multiple lines to represent a multiple mapping of the segment, only one of these records should have the secondary alignment flag bit (0x100) unset. RNEXT and PNEXT point to the primary line of the next read in the template.

   2. SEQ and QUAL of secondary alignments should be set to ’*’ to reduce the file size.

6. Optional tags:

   1. If the template has more than 2 segments, the TC tag should be present.

   2. The NM tag should be present.

7. Circular reference sequences

   Mappings that cross the coordinate ‘join’ in circular reference sequences (i.e., those whose @SQ headers specify TP:circular) may be represented as follows:

   1. (Preferred) As usual POS should be between 1 and the @SQ header’s LN value, but POS plus the sum of the lengths of CIGAR operations may exceed LN. Coordinates greater than LN are interpreted by subtracting LN so that bases at $\texttt{LN}+1, \texttt{LN}+2, \texttt{LN}+3, \ldots$ are considered to be mapped at positions $1,2,3,\ldots$; thus each (1-based) position $p$ is interpreted as $((p-1)\bmod\texttt{LN})+1$. ¹¹

   2. Alternatively, such alignments may be split across several records: one record representing the initial portion of the segment ending at LN, one representing the final portion starting from 1, and any other records representing additional portions in between spanning the entire reference sequence. One record (chosen arbitrarily) is considered primary and the remainder have their supplementary flag bit (0x800) set.

8. Annotation dummy reads: These have SEQ set to , FLAG bits 0x100 and 0x200 set (secondary and filtered), and a CT tag.

   1. If you wish to store free text in a CT tag, use the key value Note (uppercase N) to match GFF3.

   2. Multi-segment annotation (e.g., a gene with introns) should be described with multiple lines in SAM (like a multi-segment read). Where there is a clear biological direction (e.g., a gene), the first segment (FLAG bit 0x40) is used for the first section (e.g., the $5'$ end of the gene). Thus a GenBank entry location like complement(join(85052..85354, 85441..85621, 86097..86284)) would have three lines in SAM with a common QNAME:

      	FLAG	POS	CIGAR	Optional fields
      The $5'$ fragment	883 (0x373)	86097	188M	FI:i:1TC:i:3
      Middle fragment	819 (0x333)	85441	181M	FI:i:2TC:i:3
      The $3'$ fragment	947 (0x3B3)	85052	303M	FI:i:3TC:i:3

   3. If converting GFF3 to SAM, store any key, values from column 9 in the CT tag, except for the unique ID which is used for the QNAME. GFF3 columns 1 (seqid), 4 (start) and 5 (end) are encoded using SAM columns RNAME, POS and CIGAR to hold the length. GFF3 columns 3 (type) and 7 (strand) are stored explicitly in the CT tag. Remaining GFF3 columns 2 (source), 6 (score), and 8 (phase) are stored in the CT tag using key values FSource, FScore and FPhase (uppercase keys are restricted in GFF3, so these names avoid clashes). Split location features are described with multiple lines in GFF3, and similarly become multi-segment dummy reads in SAM, with the RNEXT and PNEXT columns filled in appropriately. In the absence of a convention in SAM/BAM for reads wrapping the origin of a circular genome, any GFF3 feature line wrapping the origin must be split into two segments in SAM.

3 Guide for Describing Assembly Sequences in SAM#

3.1 Unpadded versus padded representation#

To describe alignments, we can regard the reference sequence with no respect to other alignments against it. Such a reference sequence is called an unpadded reference. A position on an unpadded reference, referred to as an unpadded position, is not affected by any alignments. When we use unpadded references and positions to describe alignments, we say we are using the unpadded representation.

Alternatively, to describe the same alignments, we can modify the reference sequence to contain pads that make room for sequences inserted relative to the reference. A pad is effectively a gap and conventionally represented by an asterisk ’*’. A reference sequence containing pads is called a padded reference. A position which counts the *‘s is referred to as a padded position. A padded reference sequence may be affected by the query alignments and because of gap insertions is typically longer than the unpadded reference. The padded position of one query alignment may be affected by other query alignments.

Unpadded and padded are different representations of the same alignments. They are convertible to each other with no loss of any information. The unpadded representation is more common due to the convenience of a fixed coordinate system, while the padded representation has the advantage that alignments can be simply described by the start and end coordinates without using complex CIGAR strings. SAM traditionally uses the padded representation for de novo assembly. The ACE assembly format uses the padded representation exclusively.

3.2 Padded SAM#

The SAM format is typically used to describe alignments against an unpadded reference sequence, but it is also able to describe alignments against a padded reference. In the latter case, we say we are using a padded SAM. A padded SAM is a valid SAM, but with the difference that the reference and positions in use are padded. There may be more than one way to describe the padded representation. We recommend the following; see also the discussion in Cock et al. ¹²

In a padded SAM, alignments and coordinates are described with respect to the padded reference sequence. Unlike traditional padded representations like the ACE file format where pads/gaps are recorded in reads using *‘s, we do not write *‘s in the SEQ field of the SAM format.¹³ Instead, we describe pads in the query sequences as deletions from the padded reference using the CIGAR ‘D’ operation. In a padded SAM, the insertion and padding CIGAR operations (‘I’ and ‘P’) are not used because the padded reference already considers all the insertions.

The following shows the padded SAM for the example alignment in Section 1.1. Notably, the length of ref is 47 instead of 45. POS of the last three alignments are all shifted by 2. CIGAR of alignments bridging the 2bp insertion are also changed.

@HD VN:1.6 SO:coordinate @SQ SN:ref LN:47 ref 516 ref 1 0 14M2D31M * 0 0 AGCATGTTAGATAAGATAGCTGTGCTAGTAGGCAGTCAGCGCCAT * r001 99 ref 7 30 14M1D3M = 39 41 TTAGATAAAGGATACTG * * 768 ref 8 30 1M * 0 0 * * CT:Z:.;Warning;Note=Ref wrong? r002 0 ref 9 30 3S6M1D5M * 0 0 AAAAGATAAGGATA * PT:Z:1;4;+;homopolymer r003 0 ref 9 30 5H6M * 0 0 AGCTAA * NM:i:1 r004 0 ref 18 30 6M14N5M * 0 0 ATAGCTTCAGC * r003 2064 ref 31 30 6H5M * 0 0 TAGGC * NM:i:0 r001 147 ref 39 30 9M = 7 -41 CAGCGGCAT * NM:i:1

Here we also exemplify the recommended practice for storing the reference sequence and the reference annotations in SAM when necessary. For a reference sequence in SAM, QNAME should be identical to RNAME, POS set to 1 and FLAG to 516 (filtered and unmapped); for an annotation, FLAG should be set to 768 (filtered and secondary) with no restriction to QNAME. Dummy reads for annotation would typically have a CT tag to hold the annotation information; see the discussion of dummy reads in Section 2. See also the separate Optional Fields Specification for full details of the CT and PT annotation tags. ¹⁴

4 The BAM Format Specification#

4.1 The BGZF compression format#

BGZF is block compression implemented on top of the standard gzip file format.¹⁵ The goal of BGZF is to provide good compression while allowing efficient random access to the BAM file for indexed queries. The BGZF format is ‘gunzip compatible’, in the sense that a compliant gunzip utility can decompress a BGZF compressed file.¹⁶

A BGZF file is a series of concatenated BGZF blocks, each no larger than 64 KiB both before and after compression. Each BGZF block is itself a spec-compliant gzip archive which contains an “extra field” in the format described in RFC1952. The gzip file format allows the inclusion of application-specific extra fields and these are ignored by compliant decompression implementation. The gzip specification also allows gzip files to be concatenated. The result of decompressing concatenated gzip files is the concatenation of the uncompressed data.

Each BGZF block contains a standard gzip file header with the following standard-compliant extensions:

1. The F.EXTRA bit in the header is set to indicate that extra fields are present.

2. The extra field used by BGZF uses the two subfield ID values 66 and 67 (ASCII ‘BC’).

3. The length of the BGZF extra field payload (field LEN in the gzip specification) is 2 (two bytes of payload).

4. The payload of the BGZF extra field is a 16-bit unsigned integer in little endian format. This integer gives the size of the containing BGZF block minus one.

On disk, a complete BGZF file is a series of blocks as shown in the following table. (All integers are little endian as is required by RFC1952.)

The random access method to be described next limits the uncompressed contents of each BGZF block to a maximum of $2^{16}$ bytes of data. Thus while ISIZE is stored as a uint32_t as per the gzip format, in BGZF it is limited to the range $[0,65536]$. BSIZE can represent BGZF block sizes in the range $[1,65536]$, though typically BSIZE will be rather less than ISIZE due to compression.

4.1.1 Random access#

BGZF files support random access through the BAM file index. To achieve this, the BAM file index uses virtual file offsets into the BGZF file. Each virtual file offset is an unsigned 64-bit integer, defined as: coffset 16124uoffset, where coffset is an unsigned byte offset into the BGZF file to the beginning of a BGZF block, and uoffset is an unsigned byte offset into the uncompressed data stream represented by that BGZF block. Virtual file offsets can be compared, but subtraction between virtual file offsets and addition between a virtual offset and an integer are both disallowed.

4.1.2 End-of-file marker#

An end-of-file (EOF) trailer or marker block should be written at the end of BGZF files, so that unintended file truncation can be easily detected. The EOF marker block is a particular empty BGZF block encoded with the default zlib compression level settings, and consists of the following 28 hexadecimal bytes:

The presence of this EOF marker at the end of a BGZF file indicates that the immediately following physical EOF is the end of the file as intended by the program that wrote it. Empty BGZF blocks are not otherwise special; in particular, the presence of an EOF marker block does not by itself signal end of file.

The absence of this final EOF marker should trigger a warning or error soon after opening a BGZF file where random access is available. When reading a BGZF file in sequential streaming fashion, ideally this EOF check should be performed when the end of the stream is reached. Checking that the final BGZF block in the file decompresses to empty or checking that the last 28 bytes of the file are exactly the bytes above are both sufficient tests; each is likely more convenient in different circumstances.

4.2 The BAM format#

BAM is compressed in the BGZF format. All multi-byte numbers in BAM are little-endian, regardless of the machine endianness. The format is formally described in the following table where values in brackets are the default when the corresponding information is not available; an underlined word in uppercase denotes a field in the SAM format.

Most length and count fields described as uint32_t have additional constraints on their range: $\mathsf{l}\_\textit{text} < 2^{31}$ due to implementation limits; $\mathsf{n}\_\textit{ref} < 2^{31}$ because refID and next_refID are signed; $\mathsf{l}\_\textit{ref} < 2^{31}$ because tlen is signed; those marked “limited” are limited by available memory and the practical size of the data represented well before they are limited by, e.g., Java’s signed 32-bit integer maximum array size.

4.2.1 BIN field calculation#

BIN is calculated using the reg2bin() function in Section 5.3. For mapped reads this uses $\sf \textit{POS}-1$ (i.e., 0-based left position) and the alignment end point using the alignment length from the CIGAR string. For unmapped reads (e.g., paired-end reads where only one part is mapped, see Section 2) and reads whose CIGAR strings consume no reference bases at all, the alignment is treated as being of length one. Note unmapped reads with POS 0 (which becomes $-1$ in BAM) therefore use $\sf \textit{reg2\textit{bin}}(-1, 0)$ which is computed as 4680.

4.2.2 N_CIGAR_OP field#

With 16 bits, n_cigar_op can keep at most 65535 CIGAR operations in BAM files. For an alignment with more CIGAR operations, BAM stores the real CIGAR, encoded the same way as the cigar field in BAM, in the CG optional tag of type ‘B,I’, and sets CIGAR to ‘kSmN’ as a placeholder, where ‘k’ equals l_seq, ‘m’ is the reference sequence length in the alignment, and ‘S’ and ‘N’ are the soft-clipping and reference-clip CIGAR operators, respectively—i.e., in the binary form, n_cigar_op=2 and cigar=[k 4,m 4]. If tag CG is present and the first CIGAR operation clips the entire read, a BAM parsing library is expected to update n_cigar_op and cigar with the real CIGAR stored in the CG tag and remove the now-redundant CG tag.

4.2.3 SEQ and QUAL encoding#

Sequence is encoded in 4-bit values, with adjacent bases packed into the same byte starting with the highest 4 bits first. When l_seq is odd the bottom 4 bits of the last byte are undefined, but we recommend writing these as zero. The case-insensitive base codes ‘=ACMGRSVTWYHKDBN’ are mapped to $[0,15]$ respectively with all other characters mapping to ‘N’ (value 15).

Omitted sequence, represented in SAM as ”, is represented by l_seq being 0 and seq and qual zero-length.

Base qualities are stored as bytes in the range $[0,93]$, without any +33 conversion to printable ASCII. When base qualities are omitted but the sequence is not, qual is filled with 0xFF bytes (to length l_seq).

4.2.4 Auxiliary data encoding#

Optional alignment fields are stored immediately after each other immediately following the qual field, and are included in block_size. Each field is represented as a two-character tag followed by a single type character and then its value, whose length is determined by the field’s type.

Single character ‘A’ fields have a total length of 4 bytes, with the value represented as a single byte:

While all single (i.e., non-array) integer types are stored in SAM as ‘i’, in BAM any of ‘cCsSiI’ may be used together with the correspondingly-sized binary integer value, chosen according to the field value’s magnitude. ¹⁷ Similarly floating point ‘f’ fields are represented as IEEE 754-2008 binary32 values. Thus BAM numeric fields have a total length of 4, 5, or 7 bytes:

String fields and hex-formatted byte arrays are represented as NUL-terminated text strings: ¹⁸

The representation of a ‘B’ array field starts with a sub-type character similar to the numeric field types above and a count (uint32_t, but limited by memory and block_size) giving the number of elements in the array. The array elements follow, encoded as binary integers or IEEE floats sized according to the sub-type:

5 Indexing BAM#

Indexing aims to achieve fast retrieval of alignments overlapping a specified region without going through the whole alignments. BAM must be sorted by the reference ID and then the leftmost coordinate before indexing.

This section describes the binning scheme underlying coordinate-sorted BAM indices and its implementation in the long-established BAI format. The CSI format documented elsewhere uses a similar binning scheme and can also be used to index BAM.

5.1 Algorithm#

5.1.1 Basic binning index#

The UCSC binning scheme was suggested by Richard Durbin and Lincoln Stein and is explained in Kent et al. In this scheme, each bin represents a contiguous genomic region which is either fully contained in or non-overlapping with another bin; each alignment is associated with a bin which represents the smallest region containing the entire alignment. The binning scheme is essentially a representation of R-tree. A distinct bin uniquely corresponds to a distinct internal node in a R-tree. Bin A is a child of Bin B if the region represented by A is contained in B.

To find the alignments that overlap a specified region, we need to get the bins that overlap the region, and then test each alignment in the bins to check overlap. To quickly find alignments associated with a specified bin, we can keep in the index the start file offsets of chunks of alignments which all have the bin. As alignments are sorted by the leftmost coordinates, alignments having the same bin tend to be clustered together on the disk and therefore usually a bin is only associated with a few chunks. Traversing all the alignments having the same bin usually needs a few seek calls. Given the set of bins that overlap the specified region, we can visit alignments in the order of their leftmost coordinates and stop seeking the rest when an alignment falls outside the required region. This strategy saves half of the seek calls in average.

In the BAI format, each bin may span $2^{29}$, $2^{26}$, $2^{23}$, $2^{20}$, $2^{17}$ or $2^{14}$ bp. Bin 0 spans a 512Mbp region, bins 1–8 span 64Mbp, 9–72 8Mbp, 73–584 1Mbp, 585–4680 128kbp, and bins 4681–37448 span 16kbp regions. This implies that this index format does not support reference chromosome sequences longer than $2^{29}-1$.

The CSI format generalises the sizes of the bins, and supports reference sequences of the same length as are supported by SAM and BAM.

5.1.2 Reducing small chunks#

Around the boundary of two adjacent bins, we may see many small chunks with some having a shorter bin while the rest having a larger bin. To reduce the number of seek calls, we may join two chunks having the same bin if they are close to each other. After this process, a joined chunk will contain alignments with different bins. We need to keep in the index the file offset of the end of each chunk to identify its boundaries.

5.1.3 Combining with linear index#

For an alignment starting beyond 64Mbp, we always need to seek to some chunks in bin 0, which can be avoided by using a linear index. In the linear index, for each tiling 16384bp window on the reference, we record the smallest file offset of the alignments that overlap with the window. Given a region [rbeg, rend), we only need to visit a chunk whose end file offset is larger than the file offset of the 16kbp window containing rbeg.

With both binning and linear indices, we can retrieve alignments in most of regions with just one seek call.

5.1.4 A conceptual example#

Suppose we have a genome shorter than 144kbp. We can design a binning scheme which consists of three types of bins: bin 0 spans 0-144kbp, bin 1, 2 and 3 span 48kbp and bins from 4 to 12 span 16kbp each:

An alignment starting at 65kbp and ending at 67kbp would have a bin number 8, which is the smallest bin containing the alignment. Similarly, an alignment starting at 51kbp and ending at 70kbp would go to bin 2, while an alignment between [40k, 49k] to bin 0. Suppose we want to find all the alignments overlapping region [65k, 71k). We first calculate that bin 0, 2 and 8 overlap with this region and then traverse the alignments in these bins to find the required alignments. With a binning index alone, we need to visit the alignment at [40k, 49k] as it belongs to bin 0. But with a linear index, we know that such an alignment stops before 64kbp and cannot overlap the specified region. A seek call can thus be saved.

5.2 The BAI index format for BAM files#

The index file may optionally contain additional metadata providing a summary of the number of mapped and placed unmapped read-segments per reference sequence, and of any unplaced unmapped read-segments.¹⁹ This is stored in an optional extra metadata pseudo-bin for each reference sequence, and in the optional trailing n_no_coor field at the end of the file.

The pseudo-bins appear in the references’ lists of distinct bins as bin number 37450 (which is beyond the normal range) and are laid out so as to be compatible with real bins and their chunks:

The ref_beg/ref_end fields locate the first and last reads on this reference sequence, whether they are mapped or placed unmapped. Thus they are equal to the minimum chunk_beg and maximum chunk_end respectively.

5.3 C source code for computing bin number and overlapping bins#

The following functions compute bin numbers and overlaps for a BAI-style binning scheme with 6 levels and a minimum bin size of $2^{14}$ bp. See the CSI specification for generalisations of these functions designed for binning schemes with arbitrary depth and sizes.

When these functions are called with regions representing unplaced unmapped reads, e.g., $\sf \textit{reg2\textit{bin}}(-1, 0)$, they involve operations such as (-1)>>14 which are undefined or implementation-defined in some programming languages. They must be implemented as if these operations use the common two’s-complement semantics: $\sf \textit{reg2\textit{bin}}(-1, 0) = 4680$ and $\sf \textit{reg2\textit{bins}}(-1, 0, \ldots)$ returns $[\,0, 0, 8, 72, 584, 4680\,]$.

/* calculate bin given an alignment covering [beg,end) (zero-based, half-closed-half-open) */
int reg2bin(int beg, int end)
{
    --end;
    if (beg>>14 == end>>14) return ((1<<15)-1)/7 + (beg>>14);
    if (beg>>17 == end>>17) return ((1<<12)-1)/7 + (beg>>17);
    if (beg>>20 == end>>20) return ((1<<9)-1)/7  + (beg>>20);
    if (beg>>23 == end>>23) return ((1<<6)-1)/7  + (beg>>23);
    if (beg>>26 == end>>26) return ((1<<3)-1)/7  + (beg>>26);
    return 0;
}
/* calculate the list of bins that may overlap with region [beg,end) (zero-based) */
#define MAX_BIN (((1<<18)-1)/7)
int reg2bins(int beg, int end, uint16_t list[MAX_BIN])
{
    int i = 0, k;
    --end;
    list[i++] = 0;
    for (k =    1 + (beg>>26); k <=    1 + (end>>26); ++k) list[i++] = k;
    for (k =    9 + (beg>>23); k <=    9 + (end>>23); ++k) list[i++] = k;
    for (k =   73 + (beg>>20); k <=   73 + (end>>20); ++k) list[i++] = k;
    for (k =  585 + (beg>>17); k <=  585 + (end>>17); ++k) list[i++] = k;
    for (k = 4681 + (beg>>14); k <= 4681 + (end>>14); ++k) list[i++] = k;
    return i;
}