©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