Efficient identification of equivalences in dynamic graphs and pedigree structures

Area of Science:

• Computational Biology
• Graph Theory
• Bioinformatics

Background:

• Complex data structures, such as identity-by-descent (IBD) graphs in pedigree analysis, often vary with parameters like genetic marker position.
• Analyzing these dynamic structures requires efficient methods for testing and querying properties like equality, set operations, and equivalence classes.

Purpose of the Study:

• To introduce a new, versatile framework for designing test and query functions for complex, parameter-varying structures.
• To address the challenge of analyzing unlabeled graph nodes identified solely by their connections, as seen in IBD graphs.
• To provide a theoretical and algorithmic foundation for analyzing dynamic structures.

Main Methods:

• The proposed framework utilizes a minimal set of operations to build a range of testing functions.
• It is designed to handle structures where nodes are unlabeled and identified by edges.
• Theoretical properties and algorithmic efficiency are rigorously analyzed and proven.

Main Results:

• The framework is demonstrated to be effective for various operations, including equality testing, set operations, isolating unique states, duplication counting, and finding equivalence classes.
• It successfully addresses the constraints of unlabeled nodes in IBD graphs.
• Computational simulations confirm the approach's effectiveness.

Conclusions:

• The introduced framework offers a powerful and flexible method for analyzing complex, dynamic structures, particularly IBD graphs.
• It provides a unified approach to various analytical operations with proven theoretical and algorithmic underpinnings.
• The method is computationally efficient and effective for practical applications in bioinformatics and related fields.