| Restricted DCJ Model: Rearrangement Problems with Chromosome Reincorporation. | |
| | |
MedLine Citation:
|
PMID: 21899428 Owner: NLM Status: In-Data-Review |
Abstract/OtherAbstract:
|
Abstract We study three classical problems of genome rearrangement-sorting, halving, and the median problem-in a restricted double cut and join (DCJ) model. In the DCJ model, introduced by Yancopoulos et al., we can represent rearrangement events that happen in multichromosomal genomes, such as inversions, translocations, fusions, and fissions. Two DCJ operations can mimic transpositions or block interchanges by first extracting an appropriate segment of a chromosome, creating a temporary circular chromosome, and then reinserting it in its proper place. In the restricted model, we are concerned with multichromosomal linear genomes and we require that each circular excision is immediately followed by its reincorporation. Existing linear-time DCJ sorting and halving algorithms ignore this reincorporation constraint. In this article, we propose a new algorithm for the restricted sorting problem running in O(n log n) time, thus improving on the known quadratic time algorithm. We solve the restricted halving problem and give an algorithm that computes a multilinear halved genome in linear time. Finally, we show that the restricted median problem is NP-hard as conjectured. |
| | |
Authors:
|
Jakub Kováč; Robert Warren; Marília D V Braga; Jens Stoye |
Related Documents
:
|
12501278 - Use of 16s rdna community fingerprints to study cricket hindgut microbial communities. 18187798 - Evidence for suppression of onchocerca volvulus transmission in the oaxaca focus in mex... 22122718 - Therapists' attachment, patients' interpersonal problems and alliance development over ... 21657758 - Addressing the y2k challenge. 18820398 - Right leisure: serious, casual, or project-based? 10115708 - Reactions of beginning counselors to situations involving death and dying. |
Publication Detail:
|
Type: Journal Article |
Journal Detail:
|
Title: Journal of computational biology : a journal of computational molecular cell biology Volume: 18 ISSN: 1557-8666 ISO Abbreviation: J. Comput. Biol. Publication Date: 2011 Sep |
Date Detail:
|
Created Date: 2011-09-08 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9433358 Medline TA: J Comput Biol Country: United States |
Other Details:
|
Languages: eng Pagination: 1231-41 Citation Subset: IM |
Affiliation:
|
1 Department of Computer Science, Faculty of Mathematics, Physics, and Informatics, Comenius University , Bratislava, Slovakia . |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Theory and practice of ultra-perfection.
Next Document: The complexity of the gapped consecutive-ones property problem for matrices of bounded maximum degre...