NDLI: Constructing a gene team tree in almost O (n lg n) time

Content Provider	ACM Digital Library
Author	Wang, Biing-Feng Yang, I-Tse Lin, Chien-Hsin
Copyright Year	2014
Abstract	An important model of a conserved gene cluster is called the gene team model, in which a chromosome is defined to be a permutation of distinct genes and a gene team is defined to be a set of genes that appear in two or more species, with the distance between adjacent genes in the team for each chromosome always no more than a certain threshold δ. A gene team tree is a succinct way to represent all gene teams for every possible value of δ. The previous fastest algorithm for constructing a gene team tree of two chromosomes requires $\textit{O}(\textit{n}$ lg $\textit{n}$ lglg $\textit{n})$ time, which was given by Wang and Lin. Its bottleneck is a problem called the maximum-gap problem. In this paper, by presenting an improved algorithm for the maximum-gap problem, we reduce the upper bound of the gene team tree problem to $\textit{O}(\textit{n}$ lg $\textit{n}$ $α(\textit{n})).$ Since a grows extremely slowly, this result is almost as efficient as the current best upper bound, $\textit{O}(\textit{n}$ lg $\textit{n}),$ for finding the gene teams of a fixed δ value. Our new algorithm is very efficient from both the theoretical and practical points of view. Wang and Lin's gene-team-tree algorithm can be extended to $\textit{k}$ chromosomes with complexity $\textit{O}(\textit{kn}$ lg $\textit{n}$ lglg $\textit{n}).$ Similarly, our improved algorithm for the maximum-gap problem reduces this running time to $\textit{O}(\textit{kn}$ lg $\textit{n}$ $α(\textit{n})).$ In addition, it also provides new upper bounds for the gene team tree problem on general sequences, in which multiple copies of the same gene are allowed.
Starting Page	142
Ending Page	153
Page Count	12
File Format	PDF
ISSN	15455963
DOI	10.1109/TCBB.2013.150
Volume Number	11
Issue Number	1
Journal	IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-01-01
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Algorithms Comparative genomics Conserved gene clusters Data structures Gene teams
Content Type	Text
Resource Type	Article
Subject	Genetics Biotechnology Applied Mathematics

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

Constructing a Gene Team Tree in Almost $O$$(n; {rm lg}; n)$ Time

Improved Algorithms for Finding Gene Teams and Constructing Gene Team Trees

Improved Algorithms for Finding Gene Teams and Constructing Gene Team Trees

A New Efficient Algorithm for the Gene-Team Problem on General Sequences

A New Efficient Algorithm for the Gene-Team Problem on General Sequences

Output-Sensitive Algorithms for Finding the Nested Common Intervals of Two General Sequences

Output-Sensitive Algorithms for Finding the Nested Common Intervals of Two General Sequences

A Unified Approach for Reconstructing Ancient Gene Clusters

A Unified Approach for Reconstructing Ancient Gene Clusters

Constructing a gene team tree in almost O (n lg n) time

Similar Documents

Constructing a Gene Team Tree in Almost $O$$(n; {rm lg}; n)$ Time

Improved Algorithms for Finding Gene Teams and Constructing Gene Team Trees

Improved Algorithms for Finding Gene Teams and Constructing Gene Team Trees

A New Efficient Algorithm for the Gene-Team Problem on General Sequences

A New Efficient Algorithm for the Gene-Team Problem on General Sequences

Output-Sensitive Algorithms for Finding the Nested Common Intervals of Two General Sequences

Output-Sensitive Algorithms for Finding the Nested Common Intervals of Two General Sequences

A Unified Approach for Reconstructing Ancient Gene Clusters

A Unified Approach for Reconstructing Ancient Gene Clusters

Constructing a gene team tree in almost O (n lg n) time