Naslov
Efficient Estimation of Pairwise Distances between Genomes

Autori
Domazet-Lošo, Mirjana ; Haubold, Bernhard

Izvornik
Bioinformatics (1367-4803) 25 (2009), 24; 3221-3227

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
genome comparison; alignment-free estimator; suffix tree

Sažetak
Genome comparison is central to contemporary genomics and it typically relies on sequence alignment. However, genome-wide alignments are difficult to compute. We have therefore recently developed an accurate alignment-free estimator of the number of substitutions per site based on the lengths of exact matches between pairs of sequences. The previous implementation of this measure requires n(n − 1) suffix tree constructions and traversals, where n is the number of sequences analyzed. This does not scale well for large n. We present an algorithm to extract n(n-1)/2 pairwise distances in a single traversal of a single suffix tree containing n sequences. As a result, the run time of the suffix tree construction phase of our algorithm is reduced from O(n^2L) to O(nL), where L is the length of each sequence. We implement this algorithm in the program kr version 2 and apply it to 825 HIV genomes, 13 genomes of enterobacteria and the complete genomes of 12 Drosophila species. We show that, depending on the input data set, the new program is at least 10 times faster than its predecessor.

Izvorni jezik
Engleski

Znanstvena područja
Biologija, Računarstvo

POVEZANOST RADA