Coordinate systems for supergenomes.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Rapid advancements in sequencing technologies generate vast amounts of genome data.
• There is a growing need for effective methods in comparative and evolutionary genomics.
• Current tools for visualizing multi-species omics data are insufficient, highlighting the need for a common coordinate system.

Purpose of the Study:

• To address the lack of efficient tools for multi-species comparative genomics analysis.
• To establish a common coordinate system for diverse genomes.
• To enable large-scale evolutionary studies by overcoming limitations of single-reference genomes.

Main Methods:

• Formally modeling the problem of ordering and orienting local alignments across multiple genomes.
• Framing the problem as a variant of the NP-hard Betweenness Problem.
• Developing heuristic simplifiers to resolve ordering conflicts for practical applications.

Main Results:

• Identified the computational challenge in creating co-linear genome alignments across species.
• Demonstrated that the problem can be modeled as a Betweenness Problem variant.
• Introduced effective heuristic methods to manage computational complexity.

Conclusions:

• Heuristic simplifiers enable the computation of good common coordinate systems.
• Benchmarks on bacterial and fly genomes confirm the feasibility of the approach.
• The developed methods facilitate robust comparative genomic analyses across multiple species.