Genomic matrix medians

• Grant number: 25/05185-6
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: June 01, 2025
• End date: December 31, 2025
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: João Meidanis
• Grantee: Victor de Moraes
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

When comparing genomes, a fundamental notion is the distance between genomes. Many proposals have been put forward in recent decades, including DCJ, SCJ, breakpoint distance, rank distance and natural distance. The median genome between three genomes A, B and C is the M genome that minimizes the sum of the distances d(A,M), d(B,M) and d(C,M). Polynomial-time algorithms for calculating medians with respect to the rank distance have been proposed, but these algorithms do not always return a genome. In this project, we will focus on the rank distance, examining existing fast algorithms for medians in this paradigm and looking for ways to try to correct responses so that they are genomic, without prejudice (or with little harm) to their condition as medians. (AU)