1. Sciortino M, Mantaci S, Restivo A, Rosone G
A new sequence distance measure based on the Burrows- Wheeler Transform
Meeting: BITS 2005 - Year: 2005
Full text in a new tab
Topic: Computer algorithms and applications
Abstract: The recent developments in sequencing genomes have given a new direction to bioinformatic research. Actually, the possibility of sequencing the whole genome has raised the question of discovering common features between biological sequences corresponding to different species, reflecting on common evolutionary and functional mechanisms. This reason has led researchers to look for a definition of a distance measure on sequences able to capture these common mechanisms. Most of the traditional methods for comparing biological sequences were based on the technique of sequence alignment. Nevertheless, sequence alignment considers only local mutations of the genome, therefore it is not suitable to measure events like segment rearrangements, that involve longer genomic sequences. For this reason some alignment free distance measures have been recently introduced (see [VinAl] for a survey) and most of them are based on the concept of information theory and data compression (cf. [OS, LV, CV, EMS, BCL]). Such measures are more suitable to deal with the problem of whole genome phylogeny. The intuitive idea is that the more similar two sequences are, the more effective their joint compression is than their independent compression. We introduce a new alignment free method for comparing sequences that, differently from other ones, is combinatorial by nature and does not make use of any compressor nor any information theoretic notion.