SPRING

SPRING computes minimum series of genome rearrangements (reversals and block-interchanges) and breakpoint distances between linear or circular chromosomal genomes to analyze chromosomal evolution.

Key Features:

• Input support: Accepts linear and circular chromosomes and accepts sequence data or gene/landmark order data, including bacterial-size datasets.
• Landmark identification: When provided with sequence data, automatically identifies identical landmarks (homologous or conserved regions) among input sequences.
• Rearrangement computation: Computes a minimum series of genome rearrangements necessary to transform one chromosome into another, including reversals and block-interchanges.
• Breakpoint distance: Calculates breakpoint distance between any pair of input chromosomes.
• Algebraic algorithm: Leverages permutation-group algebra to compute rearrangement transformations.
• Phylogeny reconstruction: Reconstructs phylogenetic trees based on computed rearrangement and breakpoint distances.

Scientific Applications:

• Chromosomal evolution analysis: Assesses correlations between rearrangement and breakpoint distances to infer chromosomal evolution and structural changes.
• Phylogenetic inference: Produces phylogenetic trees representing evolutionary relationships among input genomes using rearrangement and breakpoint distance data.
• Comparative genomics of pathogens: Applied to circular genomic sequences of human Vibrio pathogens to predict evolutionary relationships and evaluate the role of block-interchange events.

Methodology:

Computes minimum reversal and block-interchange series, calculates breakpoint distances, automatically identifies identical landmarks from sequence data, leverages permutation-group algebra to calculate transformations, and reconstructs phylogenetic trees from the computed rearrangement and breakpoint distances.