tailieunhanh - Báo cáo sinh học: "Fast algorithms for computing sequence distances by exhaustive substring composition"

Tuyển tập các báo cáo nghiên cứu về sinh học được đăng trên tạp chí y học Molecular Biology cung cấp cho các bạn kiến thức về ngành sinh học đề tài: Fast algorithms for computing sequence distances by exhaustive substring composition. | Algorithms for Molecular Biology BioMed Central Research Fast algorithms for computing sequence distances by exhaustive substring composition Alberto Apostolico 1 2 3 and Olgert Denas 3 Address 1Academia Nazionale dei Lincei Rome Italy 2Department of Information Engineering Universitá di Padova Padova Italy and 3College of Computing Georgia Institute of Technology Atlanta Georgia USA Email Alberto Apostolico - axa@ Olgert Denas - gerti@ Corresponding authors Published 28 October 2008 Received 23 June 2008 Algorithms for Molecular Biology 2008 3 1 3 doi 1748-7188-3-13 Accepted 28 October 2008 This article is available from http content 3 1 13 2008 Apostolico and Denas licensee BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License http licenses by which permits unrestricted use distribution and reproduction in any medium provided the original work is properly cited. Open Access Abstract The increasing throughput of sequencing raises growing needs for methods of sequence analysis and comparison on a genomic scale notably in connection with phylogenetic tree reconstruction. Such needs are hardly fulfilled by the more traditional measures of sequence similarity and distance like string edit and gene rearrangement due to a mixture of epistemological and computational problems. Alternative measures based on the subword composition of sequences have emerged in recent years and proved to be both fast and effective in a variety of tested cases. The common denominator of such measures is an underlying information theoretic notion of relative compressibility. Their viability depends critically on computational cost. The present paper describes as a paradigm the extension and efficient implementation of one of the methods in this class. The method is based on the