1996-2019. All Rights Reserved. Online Journal of Bioinformatics . You may not store these pages in any form except for your own personal use. All other usage or distribution is illegal under international copyright treaties. Permission to use any of these pages in any other way besides the  before mentioned must be gained in writing from the publisher. This article is exclusively copyrighted in its entirety to OJB publications. This article may be copied once but may not be, reproduced or  re-transmitted without the express permission of the editors. This journal satisfies the refereeing requirements (DEST) for the Higher Education Research Data Collection (Australia). Linking:To link to this page or any pages linking to this page you must link directly to this page only here rather than put up your own page.



 Online Journal of Bioinformatics  

 Volume 10 (2): 233-240, 2009

An algorithm for edit distance of genome rearrangement based on seriate-block mutation.


Shubo Zhang1*, Jianhuang Lai2


1Department of Computer Science, Guangzhou Maritime College, Guangzhou, P.R. China., 2School of Information Science and Technology, Sun Yat-sen University, Guangzhou, P.R. China.




Zhang S, Lai J, An algorithm for edit distance of genome rearrangement based on seriate-block mutation, Onl J Bioinform, 10 (2): 233-240, 2009. Genome rearrangement is a new and essential research area that studies the gene orders and the evolutionary relations among gene families. In this report, we address the problem of phylogenomics based on genome rearrangement. We propose a mutation model of genome re-arrangement by considering seriate-block reversal, seriate-block transposition and seriate-block translocation simultaneously. Then we devise a 0(6n+nlogn) algorithm to compute the edit distance for two genomes. Finally, we implement our algorithm and applied it to the Baculoviridae genomes, the results support the previous hypotheses induced by other researchers using different comparative genomics approaches. It implies that seriate-block events seem to play an important role in the evolution of complete sequences.


Keywords: genome rearrangement, common genes, sorting by seriateblock mutation, edit distance, Baculoviridae genomes