Mapping sequences by parts
<p>Abstract</p> <p>Background:</p> <p>We present the <it>N</it>-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,...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2007-09-01
|
| Series: | Algorithms for Molecular Biology |
| Online Access: | http://www.almob.org/content/2/1/11 |
| _version_ | 1818064695610834944 |
|---|---|
| author | Guziolowski Carito Didier Gilles |
| author_facet | Guziolowski Carito Didier Gilles |
| author_sort | Guziolowski Carito |
| collection | DOAJ |
| description | <p>Abstract</p> <p>Background:</p> <p>We present the <it>N</it>-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 <it>N</it>-map of a sequence <it>s </it>over a sequence <it>t </it>is the best way of partitioning the first sequence into <it>N </it>parts and placing them, possibly complementary reversed, over the second sequence in order to maximize the sum of their gapless alignment scores.</p> <p>Results:</p> <p>We introduce an algorithm computing an optimal <it>N</it>-map with time complexity <it>O </it>(|<it>s</it>| × |<it>t</it>| × <it>N</it>) using <it>O </it>(|<it>s</it>| × |<it>t</it>| × <it>N</it>) memory space. Among all the numbers of parts taken in a reasonable range, we select the value <it>N </it>for which the optimal <it>N</it>-map has the most significant score. To evaluate this significance, we study the empirical distributions of the scores of optimal <it>N</it>-maps and show that they can be approximated by normal distributions with a reasonable accuracy. We test the functionality of the approach over random sequences on which we apply artificial evolutionary events.</p> <p>Practical Application:</p> <p>The method is illustrated with four case studies of pairs of sequences involving non-standard evolutionary events.</p> |
| first_indexed | 2024-12-10T14:40:05Z |
| format | Article |
| id | doaj.art-4c8a5b26876b4c409ef3254d7785c51a |
| institution | Directory Open Access Journal |
| issn | 1748-7188 |
| language | English |
| last_indexed | 2024-12-10T14:40:05Z |
| publishDate | 2007-09-01 |
| publisher | BMC |
| record_format | Article |
| series | Algorithms for Molecular Biology |
| spelling | doaj.art-4c8a5b26876b4c409ef3254d7785c51a2022-12-22T01:44:42ZengBMCAlgorithms for Molecular Biology1748-71882007-09-01211110.1186/1748-7188-2-11Mapping sequences by partsGuziolowski CaritoDidier Gilles<p>Abstract</p> <p>Background:</p> <p>We present the <it>N</it>-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 <it>N</it>-map of a sequence <it>s </it>over a sequence <it>t </it>is the best way of partitioning the first sequence into <it>N </it>parts and placing them, possibly complementary reversed, over the second sequence in order to maximize the sum of their gapless alignment scores.</p> <p>Results:</p> <p>We introduce an algorithm computing an optimal <it>N</it>-map with time complexity <it>O </it>(|<it>s</it>| × |<it>t</it>| × <it>N</it>) using <it>O </it>(|<it>s</it>| × |<it>t</it>| × <it>N</it>) memory space. Among all the numbers of parts taken in a reasonable range, we select the value <it>N </it>for which the optimal <it>N</it>-map has the most significant score. To evaluate this significance, we study the empirical distributions of the scores of optimal <it>N</it>-maps and show that they can be approximated by normal distributions with a reasonable accuracy. We test the functionality of the approach over random sequences on which we apply artificial evolutionary events.</p> <p>Practical Application:</p> <p>The method is illustrated with four case studies of pairs of sequences involving non-standard evolutionary events.</p>http://www.almob.org/content/2/1/11 |
| spellingShingle | Guziolowski Carito Didier Gilles Mapping sequences by parts Algorithms for Molecular Biology |
| title | Mapping sequences by parts |
| title_full | Mapping sequences by parts |
| title_fullStr | Mapping sequences by parts |
| title_full_unstemmed | Mapping sequences by parts |
| title_short | Mapping sequences by parts |
| title_sort | mapping sequences by parts |
| url | http://www.almob.org/content/2/1/11 |
| work_keys_str_mv | AT guziolowskicarito mappingsequencesbyparts AT didiergilles mappingsequencesbyparts |