DocumentCode :
2582935
Title :
Improving genome rearrangement phylogeny using sequence-style parsimony
Author :
Tang, Jijun ; Wang, Li-San
Author_Institution :
Dept. of Comput. Sci. & Eng., South Carolina Univ., Columbia, SC, USA
fYear :
2005
fDate :
19-21 Oct. 2005
Firstpage :
137
Lastpage :
144
Abstract :
The study of genome rearrangements, the evolutionary events that change the order and strandedness of genes within genomes, presents new opportunities for discoveries about deep evolutionary events. The best software so far, GRAPPA, solves breakpoint and inversion phylogenies by scoring each tree topology through iterative improvements of internal node gene orders. We find that the greedy hill-climbing approach means the accuracy is limited because of multiple local optima. To address this problem, we propose integration GRAPPA with MPME, a string encoding of gene adjacency relationships whose optimal internal node assignments can be determined globally in polynomial time, to provide better initializations for GRAPPA. In simulation studies, the new algorithm yields shorter tree lengths and better accuracy in phylogeny reconstruction.
Keywords :
biology computing; genetics; greedy algorithms; molecular biophysics; molecular configurations; trees (mathematics); GRAPPA; MPME; breakpoint phylogeny; deep evolutionary events; gene adjacency relationships; genome rearrangement phylogeny; greedy hill-climbing approach; internal node gene orders; inversion phylogeny; multiple local optima; phylogeny reconstruction; sequence-style parsimony; string encoding; tree topology; Bioinformatics; Biological cells; Biological information theory; Biology; Computer science; Encoding; Evolution (biology); Genomics; Phylogeny; Topology;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Bioinformatics and Bioengineering, 2005. BIBE 2005. Fifth IEEE Symposium on
Print_ISBN :
0-7695-2476-1
Type :
conf
DOI :
10.1109/BIBE.2005.39
Filename :
1544459
Link To Document :
بازگشت