A heuristic algorithm for reconstructing ancestral gene orders with duplications

Jian Ma, Aakrosh Ratan, Louxin Zhang, Webb Miller, David Haussler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Accurately reconstructing the large-scale gene order in an ancestral genome is a critical step to better understand genome evolution. In this paper, we propose a heuristic algorithm for reconstructing ancestral genomic orders with duplications. The method starts from the order of genes in modern genomes and predicts predecessor and successor relationships in the ancestor. Then a greedy algorithm is used to reconstruct the ancestral orders by connecting genes into contiguous regions based on predicted adjacencies. Computer simulation was used to validate the algorithm. We also applied the method to reconstruct the ancestral genomes of ciliate Paramecium tetraurelia.

Original languageEnglish (US)
Title of host publicationComparative Genomics - International Workshop, RECOMB-CG 2007, Proceedings
Pages122-135
Number of pages14
Volume4751 LNBI
StatePublished - 2007
Event5th Annual RECOMB Satellite Workshop on Comparative Genomics, RECOMB-CG 2007 - San Diego, CA, United States
Duration: Sep 16 2007Sep 18 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4751 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th Annual RECOMB Satellite Workshop on Comparative Genomics, RECOMB-CG 2007
CountryUnited States
CitySan Diego, CA
Period9/16/079/18/07

Keywords

  • Contiguous ancestral region
  • Duplication
  • Gene order reconstruction

ASJC Scopus subject areas

  • Computer Science(all)
  • Biochemistry, Genetics and Molecular Biology(all)
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'A heuristic algorithm for reconstructing ancestral gene orders with duplications'. Together they form a unique fingerprint.

  • Cite this

    Ma, J., Ratan, A., Zhang, L., Miller, W., & Haussler, D. (2007). A heuristic algorithm for reconstructing ancestral gene orders with duplications. In Comparative Genomics - International Workshop, RECOMB-CG 2007, Proceedings (Vol. 4751 LNBI, pp. 122-135). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4751 LNBI).