NDLI: Sorting Linear Genomes with Rearrangements and Indels

Content Provider	IEEE Xplore Digital Library
Author	Braga, M.D.V. Stoye, J.
Copyright Year	2004
Abstract	Rearrangements are mutations that can change the organization of a genome, but not its content. Examples are inversions of DNA segments, translocations of chromosome ends, fusions and fissions of chromosomes. All mentioned rearrangements can be represented by the generic Double Cut and Join (DCJ) operation. However, the DCJ operation also allows circular chromosomes to be created at intermediate steps, even if the compared genomes are linear. In this case it is more plausible to consider a restriction in which the reincorporation of a circular chromosome has to be done immediately after its creation. We call these two consecutive operations an ER composition. It has been shown that an ER composition mimics either an internal block interchange (when two segments in the same chromosome exchange their positions), or an internal transposition (the special case of a block interchange when the two segments are adjacent). The DCJ distance of two genomes is the same, regardless of this restriction, and can be computed in linear time. For comparing two genomes with unequal contents, in addition to rearrangements we have to allow insertions and deletions of DNA segments-named indels. It is already known that the distance in the model combining DCJ and indel operations can be exactly computed. Again, for linear genomes it would be more plausible to adopt a restricted version with ER compositions. This model was studied recently by da Silva et al. (BMC Bioinformatics 13, Suppl. 19, S14, 2012), but only an upper bound for the restricted DCJ-indel distance was provided. Here we first solve an open problem posed in that paper and present a very simple proof showing that the distance, which can be computed in linear time, is the same for both the unrestricted and the restricted DCJ-indel models. We then give a simpler algorithm for computing an optimal restricted DCJ-indel sorting scenario in O(n log n) time. We also relate the DCJ-indel distance to the restricted DCJ-substitution distance, which instead of indels considers a more powerful operation that allows the substitution of a DNA segment by another DNA segment. We show that the DCJ-indel distance is a 2-approximation for the restricted DCJ-substitution distance.
Sponsorship	IEEE Computer Society
Starting Page	500
Ending Page	506
Page Count	7
File Size	536646
File Format	PDF
ISSN	15455963
Volume Number	12
Issue Number	3
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-05-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Genomics Biological cells Sorting Bioinformatics Computational biology DNA double cut and join Combinatorial algorithms bioinformatics comparative genomics genome rearrangement
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Genetics Biotechnology

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Sorting linear genomes with rearrangements and indels

Approximating the DCJ distance of balanced genomes in linear time

Extending the Algebraic Formalism for Genome Rearrangements to Include Linear Chromosomes

Recombinations, chains and caps: resolving problems with the DCJ-indel model

Efficient gene orthology inference via large-scale rearrangements

Rearrangement Phylogeny of Genomes in Contig Form

DCJ-indel and DCJ-substitution distances with distinct operation costs

Inapproximability of (1,2)-Exemplar Distance

Investigating the complexity of the double distance problems

Sorting Linear Genomes with Rearrangements and Indels

Similar Documents

Sorting linear genomes with rearrangements and indels

Approximating the DCJ distance of balanced genomes in linear time

Extending the Algebraic Formalism for Genome Rearrangements to Include Linear Chromosomes

Recombinations, chains and caps: resolving problems with the DCJ-indel model

Efficient gene orthology inference via large-scale rearrangements

Rearrangement Phylogeny of Genomes in Contig Form

DCJ-indel and DCJ-substitution distances with distinct operation costs

Inapproximability of (1,2)-Exemplar Distance

Investigating the complexity of the double distance problems

Sorting Linear Genomes with Rearrangements and Indels