Reconstructing an ancestral genome using minimum segments duplications and reversals

被引:23
作者
El-Mabrouk, N [1 ]
机构
[1] Univ Montreal, Dept Informat & Rech Operat, Montreal, PQ H3C 3J7, Canada
关键词
D O I
10.1016/S0022-0000(02)00003-X
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
We consider a particular model of genomic rearrangements that takes paralogous and orthologous genes-into account. Given a particular model of evolution and an optimization criterion, the problem is to recover an ancestor of a modern genome modeled as an ordered sequence of signed genes. One direct application is to infer gene orders at the ancestral nodes of a phylogenetic tree. Implicit in the rearrangement literature is that each gene has exactly one copy in each genome. This hypothesis is clearly false for species containing several copies of highly paralogous genes, e.g. multigene families. One of the most important regional event by which gene duplication can occur has been referred to as duplication transposition. Our model of evolution takes such duplications into account. For a genome G with gene families of different sizes, the implicit hypothesis is that G has an ancestor containing exactly one copy of each gene, and that G has evolved from this ancestor through a series of duplication transpositions and sub string reversals. The question is: how can we reconstruct an ancestral genome giving rise to the minimal number of duplication transpositions and reversals? The key idea is to reduce the problem to a series of subproblems involving genomes containing at most two copies of each gene. For this simpler version, we provide tight bounds, and we describe an algorithm, based on Hatmenhalli and Pevzner graph and result, that is exact when certain conditions are verified. We then show how to use this algorithm to recover gene orders at the ancestral nodes of a phylogenetic tree. (C) 2002 Elsevier Science (USA). All rights reserved.
引用
收藏
页码:442 / 464
页数:23
相关论文
共 22 条
[1]   Sorting by transpositions [J].
Bafna, V ;
Pevzner, PA .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1998, 11 (02) :224-240
[2]  
BERGERON A, 2001, 12 ANN S COMB PATT M
[3]   Gene order breakpoint evidence in animal mitochondrial phylogeny [J].
Blanchette, M ;
Kunisawa, T ;
Sankoff, D .
JOURNAL OF MOLECULAR EVOLUTION, 1999, 49 (02) :193-203
[4]   CAGGG repeats and the pericentromeric duplication of the hominoid genome [J].
Eichler, EE ;
Archidiacono, N ;
Rocchi, M .
GENOME RESEARCH, 1999, 9 (11) :1048-1058
[5]  
El-Mabrouk, 1999, Genome Inform Ser Workshop Genome Inform, V10, P83
[6]  
El-Mabrouk N., 2001, J DISCRETE ALGORITHM, V1, P105
[7]  
El-Mabrouk N, 1999, P 3 ANN INT C COMP M, P154
[8]  
ELMABROUK N, 2000, SERIES COMPUTATIONAL, V1, P465
[9]  
ELMABROUK N, 2001, IN PRESS SIAM J COMP
[10]  
Hannenhalli S, 1995, AN S FDN CO, P581, DOI 10.1109/SFCS.1995.492588