Computational Genetic Genealogy

Why Caching Matters in Pedigree Reconstruction

Pedigree reconstruction is a computationally intensive process, involving numerous repetitive calculations. Without proper caching, these calculations would be performed repeatedly, leading to significant performance bottlenecks, especially when dealing with large datasets.

The key computational challenges that caching addresses include:

1. Repeated Likelihood Calculations: Computing the same relationship likelihoods multiple times
2. Redundant Ancestry Traversals: Finding ancestors or descendants of the same individual repeatedly
3. Multiple IBD Evaluations: Analyzing the same IBD segments in different contexts
4. Resource Constraints: Managing memory usage while maintaining computational speed

Principles of Memoization

Memoization is a fundamental caching technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again. In Bonsai v3, memoization is extensively used to optimize recursive and repetitive operations.

The general pattern for memoization in Bonsai v3 follows this structure:

def memoize(func):
    """Caches function results based on input arguments."""
    cache = {}
    
    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        # Create a key from the arguments
        key = str(args) + str(sorted(kwargs.items()))
        
        # Return cached result if available
        if key in cache:
            return cache[key]
        
        # Compute and cache the result
        result = func(*args, **kwargs)
        cache[key] = result
        return result
    
    return wrapper

This simple yet powerful technique can dramatically improve performance for functions that are called repeatedly with the same arguments, such as computing relationships between the same pairs of individuals or finding ancestors in a pedigree.

Least Recently Used (LRU) Caching

While basic memoization is effective, it can lead to unbounded memory usage as the cache grows over time. Least Recently Used (LRU) caching addresses this by maintaining a fixed-size cache, evicting the least recently used items when the cache is full.

Bonsai v3 implements LRU caching for memory-intensive operations, ensuring that the most frequently accessed results remain in memory while older, less frequently used results are discarded to conserve resources.

@lru_cache(maxsize=1000)
def find_lowest_common_ancestor(iid1, iid2, pedigree):
    # Implementation details...
    return lca

Disk-Based Persistent Caching

For long-running or multi-stage pedigree reconstruction tasks, it's valuable to persist computed results between program executions. Bonsai v3 implements disk-based caching to store computationally expensive results that can be reused across different sessions.

This is particularly important for iterative development processes where users may want to experiment with different parameters without recalculating unchanged components.

Persistent caching is especially valuable for:

• Relationship likelihood calculations that depend on complex statistical models
• Genetic segment analyses that require significant computational resources
• Intermediate results in multi-stage pedigree reconstruction

Multi-Level Caching Architecture

The most sophisticated caching strategy in Bonsai v3 is hierarchical caching, which combines multiple caching mechanisms to optimize for different types of operations and access patterns.

This approach uses multiple cache levels with different characteristics:

1. Level 1: In-memory LRU cache for the most frequently accessed items (fast access, limited size)
2. Level 2: Disk-based persistent cache for less frequently accessed items (slower access, larger size)

When a value is requested, the system checks each cache level in order, starting with the fastest. If the value is found in a slower cache, it's also stored in faster caches for future access, implementing a traditional hierarchical memory model.

class HierarchicalCache:
    def __init__(self, caches):
        self.caches = caches  # List of caches from fastest to slowest
    
    def get(self, key):
        # Check each cache level
        for i, cache in enumerate(self.caches):
            value = cache.get(key)
            if value is not None:
                # Store the value in all faster caches
                for j in range(i):
                    self.caches[j].put(key, value)
                return value
        
        return None

Where and How Caching is Applied

In Bonsai v3, caching mechanisms are strategically applied to maximize performance benefits while managing resource usage:

This strategic application of different caching mechanisms ensures that Bonsai v3 achieves optimal performance across a wide range of use cases and dataset sizes.

Measuring and Maximizing Cache Effectiveness

The effectiveness of caching in Bonsai v3 is continuously monitored and optimized through several key metrics:

• Hit Ratio: The percentage of cache lookups that result in a hit (found in cache)
• Memory Usage: The amount of memory consumed by the cache
• Cache Turnover: How frequently items are evicted from the cache

To maximize cache effectiveness, Bonsai v3 employs several optimization techniques:

1. Key Normalization: Ensuring that functionally equivalent inputs produce the same cache key
2. Selective Caching: Only caching results that are expensive to compute or likely to be reused
3. Cache Warming: Precomputing commonly used results to populate the cache
4. Adaptive Sizing: Dynamically adjusting cache sizes based on available resources and access patterns

When Caching May Not Help

While caching significantly improves performance in many scenarios, there are situations where its benefits may be limited:

• Unique Inputs: When most function calls have unique inputs, caching provides minimal benefit
• Memory Constraints: On systems with very limited memory, aggressive caching may lead to increased paging and reduced performance
• Simple Operations: For operations that are already very fast, the overhead of cache management may outweigh the benefits

Bonsai v3 addresses these limitations through adaptive caching strategies that adjust based on the specific characteristics of the dataset and available system resources.

Caching mechanisms are a critical component of Bonsai v3's performance optimization strategy, enabling efficient pedigree reconstruction even with large and complex datasets. By intelligently combining different caching approaches—from simple memoization to sophisticated hierarchical caching—Bonsai v3 achieves dramatic performance improvements while managing resource usage effectively.

In the next lab, we'll explore error handling and data validation mechanisms in Bonsai v3, which ensure robust performance even with imperfect data inputs.