NDLI: The Reconstruction of Doubled Genomes

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	El-Mabrouk, Nadia Sankoff, David
Copyright Year	2003
Abstract	The genome can be modeled as a set of strings (chromosomes) of distinguished elements called genes. Genome duplication is an important source of new gene functions and novel physiological pathways. Originally (ancestrally), a duplicated genome contains two identical copies of each chromosome, but through the genomic rearrangement mutational processes of reciprocal translocation (prefix and/or suffix exchanges between chromosomes) and substring reversals, this simple doubled structure is disrupted. At the time of observation, each of the chromosomes resulting from the accumulation of rearrangements can be decomposed into a succession of conserved segments, such that each segment appears exactly twice in the genome. We present exact algorithms for reconstructing the ancestral doubled genome in linear time, minimizing the number of rearrangement mutations required to derive the observed order of genes along the present-day chromosomes. Somewhat different techniques are required for a translocations-only model, a translocations/reversals model, both of these in the multichromosomal context (eukaryotic nuclear genomes), and a reversals-only model for single chromosome prokaryotic and organellar genomes. We apply these methods to the yeast genome, which is thought to have doubled, and to the liverwort mitochondrial genome, whose duplicate genes are unlikely to have arisen by genome doubling.
Starting Page	754
Ending Page	792
Page Count	39
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539700377177
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3
Volume Number	32
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2003-01-01
Access Restriction	Subscribed
Subject Keyword	signed genes Computational difficulty of problems reversal Analysis of algorithms and problem complexity translocation genome rearrangement genome duplication Graph algorithms exact polynomial algorithms Graph representations Hannenhalli--Pevzner graph Paths and cycles
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

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

On the reconstruction of ancient doubled circular genomes using minimum reversals (1999)

On the reconstruction of ancient doubled circular genomes using minimum reversals.

A Very Elementary Presentation of the Hannenhalli-Pevzner Theory (2003)

A Very Elementary Presentation of the Hannenhalli-Pevzner Theory (2001)

Hybridization and Genome Rearrangement

Heuristic Algorithm for Computing Reversal Distance with MultiGene Families via Binary Integer Programming

The reconstruction of doubled genomes

Odd Paths, Cycles and $T$-joins: Connections and Algorithms

Algorithms for multiple genome rearrangement by signed reversals (2003).

The Reconstruction of Doubled Genomes

Similar Documents

On the reconstruction of ancient doubled circular genomes using minimum reversals (1999)

On the reconstruction of ancient doubled circular genomes using minimum reversals.

A Very Elementary Presentation of the Hannenhalli-Pevzner Theory (2003)

A Very Elementary Presentation of the Hannenhalli-Pevzner Theory (2001)

Hybridization and Genome Rearrangement

Heuristic Algorithm for Computing Reversal Distance with MultiGene Families via Binary Integer Programming

The reconstruction of doubled genomes

Odd Paths, Cycles and $T$-joins: Connections and Algorithms

Algorithms for multiple genome rearrangement by signed reversals (2003).

The Reconstruction of Doubled Genomes