Skip Navigation

This Article
Right arrow FREE Full Text (Print PDF) Freely available
Right arrow FREE Full Text (Screen PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Bergeron, A.
Right arrow Articles by Stoye, J.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Bergeron, A.
Right arrow Articles by Stoye, J.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Bioinformatics Vol. 18 no. 90002 2002
Pages S54-S63
© 2002 Oxford University Press

Common intervals and sorting by reversals: a marriage of necessity

A. Bergeron 1,2, S. Heber 3 and J. Stoye 4

1 LaCIM, Université du Québec à Montréal, Canada
2 Institut Gaspard-Monge, Université Marne-la-Vallée, France
3 Department of Computer Science and Engineering, University of California, San Diego, USA
4 AG Genominformatik, Technische Fakultät, Universität Bielefeld, Postfach 100131, 33501 Bielefeld, Germany

Received on April 18, 2002 ; accepted on June 15, 2002

This paper revisits the problem of sorting by reversals with tools developed in the context of detecting common intervals. Mixing the two approaches yields new definitions and algorithms for the reversal distance computations, that apply directly on the original permutation.

Traditional constructions such as recasting the signed permutation as a positive permutation, or traversing the overlap graph to analyze its connected components, are replaced by elementary definitions in terms of intervals of the permutation. This yields simple linear time algorithms that identify the essential features in a single pass over the permutation and use only simple data structures like arrays and stacks.

Contact: stoye{at}TechFak.Uni-Bielefeld.DE


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 BioinformaticsHome page
J. Ebert and D. Brutlag
Development and validation of a consistency based multiple structure alignment algorithm
Bioinformatics, May 1, 2006; 22(9): 1080 - 1087.
[Abstract] [Full Text] [PDF]

Home page
 Hum Mol GenetHome page
D. A. Thompson, A. R. Janecke, J. Lange, K. L. Feathers, C. A. Hubner, C. L. McHenry, D. W. Stockton, G. Rammesmayer, J. R. Lupski, G. Antinolo, et al.
Retinal degeneration associated with RDH12 mutations results from decreased 11-cis retinal synthesis due to disruption of the visual cycle
Hum. Mol. Genet., December 15, 2005; 14(24): 3865 - 3875.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
M. Punta and B. Rost
PROFcon: novel prediction of long-range contacts
Bioinformatics, July 1, 2005; 21(13): 2960 - 2968.
[Abstract] [Full Text] [PDF]

Home page
 Protein Sci.Home page
A. Fallahi, B. Kroll, L. R. Warner, R. J. Oxford, K. M. Irwin, L. M. Mercer, S. E. Shadle, and J. T. Oxford
Structural model of the amino propeptide of collagen XI {alpha}1 chain with similarity to the LNS domains
Protein Sci., June 1, 2005; 14(6): 1526 - 1537.
[Abstract] [Full Text] [PDF]

Home page
 Protein Sci.Home page
T. Kaneko, N. Tanaka, and T. Kumasaka
Crystal structures of RsbQ, a stress-response regulator in Bacillus subtilis
Protein Sci., February 1, 2005; 14(2): 558 - 565.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
J. Shapiro and D. Brutlag
FoldMiner and LOCK 2: protein structure comparison and motif discovery on the web
Nucleic Acids Res., July 1, 2004; 32(suppl_2): W536 - W541.
[Abstract] [Full Text] [PDF]

Home page
 Protein Sci.Home page
J. Shapiro and D. Brutlag
FoldMiner: Structural motif discovery using an improved superposition algorithm
Protein Sci., January 1, 2004; 13(1): 278 - 294.
[Abstract] [Full Text] [PDF]


Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.