NDLI: Sorting Genomes by Translocations and Deletions, Dealing with Duplicated Genes

Content Provider	IEEE Xplore Digital Library
Author	Xingqin Qi Guojun Li
Copyright Year	2009
Abstract	The problem of sorting by reciprocal translocations (abbreviated as SBT) arises from the field of comparative genomics, which is to find a shortest sequence of reciprocal translocations that transforms one genome \Pi into another genome \Gamma, with the restriction that \Pi and \Gamma contain the same genes. SBT has been proved to be polynomial-time solvable, and several polynomial algorithms have been developed, including Bergeron's SBT algorithm. Recently, an algorithm allowing to compare genomes with different genes but without duplications is given by extending Bergeron's SBT algorithm. Here, we will improve the approach to handle genomes with duplicated genes. Obviously, the existence of duplications will make the problem more difficult. We should decide which one of the duplications in the subject genome \Pi should be assigned to a particular homolog in the target genome \Gamma; resolving such a problem appears to require exponential time. In this paper, by a similar method developed by Mark Marron et. al., which was used to sort two chromosomes containing different genes, we present an approximation algorithm for computing near minimal sorting sequences involving translocations and deletions between two (multi-chromosomes) genomes containing different genes allowing non-tails duplications. We derive the error bound for the polynomial-time distance computation. This is the first constant approximation algorithm for SBT with duplications.
Starting Page	179
Ending Page	183
File Size	180165
Page Count	5
File Format	PDF
ISBN	9780769535715
DOI	10.1109/GCIS.2009.51
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-05-19
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis deletions Genomics Mathematics duplications Statistics Biological cells Sorting translocations Approximation algorithms Polynomials Bioinformatics Intelligent systems
Content Type	Text
Resource Type	Article

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