Alignment-free genomic sequence comparison using FCGR and signal processing

摘要

For fairly short nucleotide sequences, of up to perhaps 100 bp, methods that are based on aligning strings can be quite powerful. These do not scale well to longer sequences. In recent decades there has thus been considerable work in developing alignment-free methods for comparing longer gene fragments. A far from exhaustive list of references is [ – ] (and an extensive review of these is found in [ ]). A key idea is to capture some aspects of the sequences, perhaps as images or numeric vectors, and apply image and/or signal processing methods in a way that is fast and allows for distance-based comparisons. One family of methods (well represented in the above references) uses the Frequency Chaos Game Representation (FCGR) [ , ] (based on earlier work by Jeffrey [ ]). This creates images with certain fractal properties that capture frequencies of -mers for modest values of (as will be explained in the “ ” subsubsection of the “ ” section). A number of different processing methods have then been deployed in order to classify these images; references [ , , , , , , – ] show several of these and convey some idea of their variety.