Alignment of minisatellite maps based on run-length encoding scheme

Area of Science:

• Genomics
• Bioinformatics
• Evolutionary Biology

Background:

• Minisatellite map evolution is driven by duplication events.
• Existing alignment algorithms struggle with alphabet dependency and map unit repetitiveness.
• Accurate alignment requires incorporating duplication costs alongside edit operations.

Purpose of the Study:

• To develop an alphabet-independent algorithm for optimal minisatellite map alignment.
• To improve computational efficiency and accuracy in sequence alignment.
• To better model the duplication mechanism in minisatellite evolution.

Main Methods:

• Algorithm based on run-length encoding for alphabet independence.
• Pre-computation of optimal duplication costs for all substrings.
• Incorporation of pre-computed costs into alignment recurrence.

Main Results:

• The new algorithm is faster and more efficient than previous methods.
• Demonstrated alphabet independence and effective use of repetitiveness.
• Derived quantitative evidence of directional bias in MSY1 minisatellite growth.

Conclusions:

• The developed algorithm offers a more general and accurate model for minisatellite map alignment.
• Run-length encoding provides a robust solution for handling repetitive sequence data.
• Findings suggest specific evolutionary pressures shaping minisatellite dynamics.