Related Experiment Video
Updated: Nov 23, 2025

Mapping Bacterial Functional Networks and Pathways in Escherichia Coli using Synthetic Genetic Arrays
Published on: November 12, 2012
Finding orthologous gene blocks in bacteria: the computational hardness of the problem and novel methods to address
Huy N Nguyen1,2, Alexey Markin2, Iddo Friedberg1,3
1Department of Veterinary Microbiology and Preventive Medicine, Iowa State University, Ames, IA 50011, USA.
Motivation:
The evolution of complexity is one of the most fascinating and challenging problems in modern biology, and tracing the evolution of complex traits is an open problem. In bacteria, operons and gene blocks provide a model of tractable evolutionary complexity at the genomic level. Gene blocks are structures of co-located genes with related functions, and operons are gene blocks whose genes are co-transcribed on a single mRNA molecule. The genes in operons and gene blocks typically work together in the same system or molecular complex. Previously, we proposed a method that explains the evolution of orthologous gene blocks (orthoblocks) as a combination of a small set of events that take place in vertical evolution from common ancestors. A heuristic method was proposed to solve this problem. However, no study was done to identify the complexity of the problem.
Results:
Here, we establish that finding the homologous gene block problem is NP-hard and APX-hard. We have developed a greedy algorithm that runs in polynomial time and guarantees an O(lnn) approximation. In addition, we formalize our problem as an integer linear program problem and solve it using the PuLP package and the standard CPLEX algorithm. Our exploration of several candidate operons reveals that our new method provides more optimal results than the results from the heuristic approach, and is significantly faster.
Availability And Implementation:
The software and data accompanying this paper are available under the GPLv3 and CC0 license respectively on: https://github.com/nguyenngochuy91/Relevant-Operon.
Related Concept Videos
Modern Molecular Taxonomy
Evolutionary Relationships through Genome Comparisons
Coordination of Gene Expression Processes in Bacteria
Applications of Molecular Taxonomy
Genome Size and the Evolution of New Genes
Genomic DNA in Prokaryotes
Genomic Diversity in Bacteria
Although bacterial genomes are much...

