A heuristic algorithm for reconstructing ancestral gene orders with duplications

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

doi:10.1007/978-3-540-74960-8_10

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 proceeding › Conference 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 language	English (US)
Title of host publication	Comparative Genomics - International Workshop, RECOMB-CG 2007, Proceedings
Publisher	Springer
Pages	122-135
Number of pages	14
ISBN (Print)	9783540749592
DOIs	https://doi.org/10.1007/978-3-540-74960-8_10
State	Published - 2007
Externally published	Yes
Event	5th Annual RECOMB Satellite Workshop on Comparative Genomics, RECOMB-CG 2007 - San Diego, CA, United States Duration: Sep 16 2007 → Sep 18 2007

Publication series

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

Other

Other	5th Annual RECOMB Satellite Workshop on Comparative Genomics, RECOMB-CG 2007
Country/Territory	United States
City	San Diego, CA
Period	9/16/07 → 9/18/07

Keywords

Contiguous ancestral region
Duplication
Gene order reconstruction

ASJC Scopus subject areas

General Computer Science
General Biochemistry, Genetics and Molecular Biology
Theoretical Computer Science

Online availability

10.1007/978-3-540-74960-8_10

Library availability

Discover UIUC Full Text

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 (pp. 122-135). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4751 LNBI). Springer. https://doi.org/10.1007/978-3-540-74960-8_10

A heuristic algorithm for reconstructing ancestral gene orders with duplications. / Ma, Jian; Ratan, Aakrosh; Zhang, Louxin et al.
Comparative Genomics - International Workshop, RECOMB-CG 2007, Proceedings. Springer, 2007. p. 122-135 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4751 LNBI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4751 LNBI, Springer, pp. 122-135, 5th Annual RECOMB Satellite Workshop on Comparative Genomics, RECOMB-CG 2007, San Diego, CA, United States, 9/16/07. https://doi.org/10.1007/978-3-540-74960-8_10

Ma J, Ratan A, Zhang L, Miller W, Haussler D. A heuristic algorithm for reconstructing ancestral gene orders with duplications. In Comparative Genomics - International Workshop, RECOMB-CG 2007, Proceedings. Springer. 2007. p. 122-135. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-74960-8_10

Ma, Jian ; Ratan, Aakrosh ; Zhang, Louxin et al. / A heuristic algorithm for reconstructing ancestral gene orders with duplications. Comparative Genomics - International Workshop, RECOMB-CG 2007, Proceedings. Springer, 2007. pp. 122-135 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{978403ce187e42a6a6a54cf945c4ee6d,

title = "A heuristic algorithm for reconstructing ancestral gene orders with duplications",

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.",

keywords = "Contiguous ancestral region, Duplication, Gene order reconstruction",

author = "Jian Ma and Aakrosh Ratan and Louxin Zhang and Webb Miller and David Haussler",

year = "2007",

doi = "10.1007/978-3-540-74960-8_10",

language = "English (US)",

isbn = "9783540749592",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "122--135",

booktitle = "Comparative Genomics - International Workshop, RECOMB-CG 2007, Proceedings",

address = "Germany",

note = "5th Annual RECOMB Satellite Workshop on Comparative Genomics, RECOMB-CG 2007 ; Conference date: 16-09-2007 Through 18-09-2007",

}

TY - GEN

T1 - A heuristic algorithm for reconstructing ancestral gene orders with duplications

AU - Ma, Jian

AU - Ratan, Aakrosh

AU - Zhang, Louxin

AU - Miller, Webb

AU - Haussler, David

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

KW - Contiguous ancestral region

KW - Duplication

KW - Gene order reconstruction

UR - http://www.scopus.com/inward/record.url?scp=38349158455&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38349158455&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-74960-8_10

DO - 10.1007/978-3-540-74960-8_10

M3 - Conference contribution

AN - SCOPUS:38349158455

SN - 9783540749592

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 122

EP - 135

BT - Comparative Genomics - International Workshop, RECOMB-CG 2007, Proceedings

PB - Springer

T2 - 5th Annual RECOMB Satellite Workshop on Comparative Genomics, RECOMB-CG 2007

Y2 - 16 September 2007 through 18 September 2007

ER -

A heuristic algorithm for reconstructing ancestral gene orders with duplications

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this