Back to Search
Start Over
Perfect Sorting by Reversals Is Not Always Difficult.
- Source :
- Algorithms in Bioinformatics; 2005, p228-238, 11p
- Publication Year :
- 2005
-
Abstract
- This paper investigates the problem of conservation of combinatorial structures in genome rearrangement scenarios. We characterize a class of signed permutations for which one can compute in polynomial time a reversal scenario that conserves all common intervals, and that is parsimonious among such scenarios. Figeac and Varré (WABI 2004) announced that the general problem is NP-hard. We show that there exists a class of permutations for which this computation can be done in linear time with a very simple algorithm, and, for a larger class of signed permutations, the computation can be achieved in subquadratic time. We apply these methods to permutations obtained from the X chromosomes of the human, mouse and rat. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540290087
- Database :
- Supplemental Index
- Journal :
- Algorithms in Bioinformatics
- Publication Type :
- Book
- Accession number :
- 32865119
- Full Text :
- https://doi.org/10.1007/11557067_19