©1996-2009
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.
OJBTM
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.
ABSTRACT
Zhang S, Lai J, An algorithm for
edit distance of genome rearrangement based on seriate-block mutation, Online J
Bioinformatics, 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