Common intervals and sorting by reversals: a marriage of necessity |
| |
Authors: | Bergeron A Heber S Stoye J |
| |
Institution: | LaCIM, Université du Québec à Montréal, Canada. |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 PubMed 等数据库收录! |
|