Method and systems for the indexing of bioinformatics data

Inventors

Alberti, Claudio • Zoia, Giorgio • Renzi, Daniele • Baluch, Mohamed Khoso

Assignees

Koninklijke Philips NV

Abstract

Method and apparatus for the indexing of genome sequence data produced by genome sequencing machines. The proposed method can be applied both to raw sequence data produced by sequencing machines and to those sequence reads that cannot be mapped on any reference sequence according to specific matching criteria. This invention describes a method to partition and index unaligned sequence reads to enable browsing and efficient selective access.

Core Innovation

The document describes an indexing/compression framework for genome sequencing data in which reads are classified according to mapping on reference sequences, and reads unmapped on the reference sequences are handled using a specific subset of syntax elements. Unmapped reads are partitioned into clusters of reads that share a common sequence or subsequence of nucleotides called a cluster signature, where membership requires either an exact and complete signature match or a number of mismatches below a defined threshold.

Clustered reads are encoded as a multiplicity of blocks of syntax elements, and the blocks are structured with header information to create successive Access Units. The cluster signatures are encoded into N-bit integer bitstrings using a defined nucleotide-to-bits encoding scheme that supports constant or variable signature length, including a terminator symbol for variable signature lengths. The clustered, encoded blocks are stored using entropy coding into Access Units together with descriptor structures and headers.

To enable selective pattern matching without decoding all data, the framework stores global information in a Genomic Dataset Header and uses a Master Index Table that associates encoded cluster signatures and integer position information with descriptor blocks within the Access Units. The disclosed decoder operations demultiplex the bitstream into Access Units, decode signatures and entropy-coded descriptor blocks, and extract reads partitioned into clusters based on the decoded cluster signatures, while using the Master Index Table and associated vectors of integer values to locate relevant Access Units and descriptor blocks for efficient browsing and selective access.

Claims Coverage

The independent claims cover three inventive features: encoding unmapped genome sequence reads into clustered, header-structured Access Units with cluster signatures, a genomic encoder architecture implementing clustering, syntax-block encoding, and Access-Unit structuring, and decoding encoded genomic data by demultiplexing Access Units by type and decoding entropy-coded syntax blocks to recover clustered reads. Across the claims, the inventive focus is on cluster-signature-based treatment of reads that do not map on reference sequences, and on structured Access Units with header information and, in refinements, a Master Index Table for selective access.

The independent claims define a workflow and corresponding encoder/decoder structures that classify reads by mapping on reference sequences, focus encoding and decoding on reads unmapped on reference sequences using cluster signatures, and encode those clustered reads as multiplicity blocks of syntax elements structured into successive Access Units with header information. Decoding demultiplexes Access Units by mapping type, entropy-decodes syntax-element blocks, and uses descriptor decoding to recover clusters of reads using the exact-match-or-mismatch-below-threshold cluster-signature rule.

Stated Advantages

Documented Applications