Bioinformatics Vol. 15 no. 11 1999
Pages 909-917
© 1999 Oxford University Press
Genome rearrangement with gene families
1 Centre de recherches mathématiques, Universitéde Montréal, CP 6128 Succursale Centre-Ville, Montréal, Québec H3C 3J7, Canada
Motivation: The theory and practice of genome rearrangement analysis breaks down in the biologically widespread contexts where each gene may be present in a number of copies, not necessarily contiguous. In some of these contexts it is, however, appropriate to ask which members of each gene family in two genomes G and H, lengths lG and lH, are its true exemplars , i.e. which best reflect the original position of the ancestral gene in the common ancestor genome. This entails a search for the two exemplar strings of same length n (= number of gene families, including singletons), having the smallest possible rearrangement distance: the exemplar distance .
Results: A branch and bound algorithm calculates these distances efficiently when based on easily calculated traditional rearrangement distances, such as signed reversals distance or breakpoint distance, which also satisfy a property of monotonicity in the number of genes. Simulations show that in two random genomes, the expected exemplar distance/n is sensitive to the number and size of gene families, but approaches 1 as the number of singleton families increases. When the basic rearrangement distance is just the number of breakpoints, the expected cost of computing the exemplar breakpoints distance (EBD), as measured by total calls to the underlying breakpoint distance routine, is highly dependent on both n and the configuration of gene families. On the other hand, basing exemplar distance on exemplar reversals distance (ERD), the expected computing cost depends on the configuration of gene families but is not sensitive to n.
Availability: Code for EBD and ERD is available from the author or may be accessed at http://www.crm.umontreal.ca/~viart/exemplar·dis.html
Contact: sankoff{at}ere.umontreal.ca
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  J. Ma, A. Ratan, B. J. Raney, B. B. Suh, W. Miller, and D. Haussler Inaugural Article: The infinite sites model of genome evolution PNAS, September 23, 2008; 105(38): 14254 - 14261. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 L.-W. Jiang, K.-L. Lin, and C. L. Lu OGtree: a tool for creating genome trees of prokaryotes based on overlapping genes Nucleic Acids Res., July 1, 2008; 36(suppl_2): W475 - W480. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. T. Nguyen, Y. C. Tay, and L. Zhang Divide-and-conquer approach for the exemplar breakpoint distance Bioinformatics, May 15, 2005; 21(10): 2171 - 2176. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 E. E. Eichler and D. Sankoff Structural Dynamics of Eukaryotic Chromosome Evolution Science, August 8, 2003; 301(5634): 793 - 797. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. Brudno, C. B. Do, G. M. Cooper, M. F. Kim, E. Davydov, N. C. S. Program, E. D. Green, A. Sidow, and S. Batzoglou LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA Genome Res., April 1, 2003; 13(4): 721 - 731. [Abstract] [Full Text] [PDF]
|
|