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: Mapping sequences by parts. | Algorithms for Molecular Biology BioMed Central Research Mapping sequences by parts Gilles Didier 1 and Carito Guziolowski2 Open Access Address 1Institut de Mathématiques de Luminy 163 avenue de Luminy Case 907 13288 Marseille Cedex 9 France. and 2Projet Symbiose IRISA - campus de Beaulieu 35042 Rennes Cedex France. Email Gilles Didier - didier@ Carito Guziolowski - cvargas@ Corresponding author Published 19 September 2007 Received 2 February 2007 Algorithms for Molecular Biology 2007 2 11 doi 1748-7188-2-11 Accepted 19 September 2007 This article is available from http content 2 1 11 2007 Didier and Guziolowski 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. Abstract Background We present the N-map method a pairwise and asymmetrical approach which allows us to compare sequences by taking into account evolutionary events that produce shuffled reversed or repeated elements. Basically the optimal N-map of a sequence s over a sequence t is the best way of partitioning the first sequence into N parts and placing them possibly complementary reversed over the second sequence in order to maximize the sum of their gapless alignment scores. Results We introduce an algorithm computing an optimal N-map with time complexity O s X t X N using O s X t X N memory space. Among all the numbers of parts taken in a reasonable range we select the value N for which the optimal N-map has the most significant score. To evaluate this significance we study the empirical distributions of the scores of optimal N-maps and show that they can be approximated by normal distributions with a reasonable accuracy. We test the .
