Document Detail


A new efficient algorithm for the gene-team problem on general sequences.
MedLine Citation:
PMID:  22282907     Owner:  NLM     Status:  MEDLINE    
Abstract/OtherAbstract:
Identifying conserved gene clusters is an important step toward understanding the evolution of genomes and predicting the functions of genes. A famous model to capture the essential biological features of a conserved gene cluster is called the gene-team model. The problem of finding the gene teams of two general sequences is the focus of this paper. For this problem, He and Goldwasser had an efficient algorithm that requires O(mn) time using O(m + n) working space, where m and n are, respectively, the numbers of genes in the two given sequences. In this paper, a new efficient algorithm is presented. Assume m ≤ n. Let C = Σ(α)(∈)(Σ) o(1)(α)o(2)(α), where Σ is the set of distinct genes, and o(1)(α) and o(2)(α) are, respectively, the numbers of copies of α in the two given sequences. Our new algorithm requires O(min{C lg n, mn}) time using O(m + n) working space. As compared with He and Goldwasser's algorithm, our new algorithm is more practical, as C is likely to be much smaller than mn in practice. In addition, our new algorithm is output sensitive. Its running time is O(lg n) times the size of the output. Moreover, our new algorithm can be efficiently extended to find the gene teams of k general sequences in O(k C lg (n(1)n(2). . .n(k)) time, where n(i) is the number of genes in the ith input sequence.
Authors:
Biing-Feng Wang; Chung-Chin Kuo; Shang-Ju Liu; Chien-Hsin Lin
Related Documents :
11398967 - Characterization of the gene encoding mouse mast cell protease 8 (mmcp-8), and a compar...
9782277 - Proteolytic processing of the polyprotein encoded by orf1b of the coronavirus infectiou...
11978977 - Characterization and comparative mapping of the porcine ctsl gene indicates a novel syn...
25216717 - Fine mapping qtl for female fertility on bta04 and bta13 in dairy cattle using hd snp a...
21965557 - Qlicrice: a web interface for abiotic stress responsive qtl and loci interaction channe...
1322527 - Characterization of an enhancer upstream from the muscle-type promoter of a gene encodi...
Publication Detail:
Type:  Journal Article; Research Support, Non-U.S. Gov't    
Journal Detail:
Title:  IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM     Volume:  9     ISSN:  1557-9964     ISO Abbreviation:  IEEE/ACM Trans Comput Biol Bioinform     Publication Date:    2012 Mar-Apr
Date Detail:
Created Date:  2012-01-27     Completed Date:  2012-03-25     Revised Date:  2012-05-03    
Medline Journal Info:
Nlm Unique ID:  101196755     Medline TA:  IEEE/ACM Trans Comput Biol Bioinform     Country:  United States    
Other Details:
Languages:  eng     Pagination:  330-44     Citation Subset:  IM    
Affiliation:
Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China. bfwang@cs.nthu.edu.tw
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Descriptor/Qualifier:
Algorithms*
Animals
Conserved Sequence*
Genome
Humans
Models, Genetic
Multigene Family*
Sequence Alignment

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine


Previous Document:  Rituximab, cyclophosphamide, doxorubicin, vincristine, and prednisone with or without radiotherapy i...
Next Document:  Time-course of effects of oral cinnarizine and hyoscine on task performance.