title: Ranking of Prokaryotic Genomes Based on Maximization of Sortedness of Gene Lengths.
abstract: How variations of gene lengths (some genes become longer than their predecessors, while other genes become shorter and the sizes of these factions are randomly different from organism to organism) depend on organismal evolution and adaptation is still an open question. We propose to rank the genomes according to lengths of their genes, and then find association between the genome rank and variousproperties, such as growth temperature, nucleotide composition, and pathogenicity. This approach reveals evolutionary driving factors. The main purpose of this study is to test effectiveness and robustness of several ranking methods. The selected method of evaluation is measuring of overall sortedness of the data. We have demonstrated that all considered methods give consistent results and Bubble Sort and Simulated Annealing achieve the highest sortedness. Also, Bubble Sort is considerably faster than the Simulated Annealing method.
authors.affiliation: Department of Evolutionary and Environmental Biology and Institute of Evolution, University of Haifa, Israel.
authors.forename: A
authors.initials: A
authors.lastname: Bolshoy
authors.affiliation: Department of Evolutionary and Environmental Biology and Institute of Evolution, University of Haifa, Israel ; Department of Computer Science, University of Haifa, Israel, Israel.
authors.forename: B
authors.initials: B
authors.lastname: Salih
authors.affiliation: Department of Evolutionary and Environmental Biology and Institute of Evolution, University of Haifa, Israel ; The Tauber Bioinformatics Research Center at University of Haifa.
authors.forename: I
authors.initials: I
authors.lastname: Cohen
authors.affiliation: Children's Hospital Los Angeles, University of Southern California, Los Angeles, California, USA.
authors.forename: T
authors.initials: T
authors.lastname: Tatarinova
keywords: Combinatorial optimization; Computational biology; Evolution; Gene length; LOPI; Simulation Annealing