Capacitated clustering problem in computational biology: Combinatorial and statistical approach for sibling reconstruction

Chun-An Chou, Wanpracha Art Chaovalitwongse, Tanya Y. Berger-Wolf, Bhaskar DasGupta, Mary V. AshleyComput. Oper. Res 2012 · DOI

TL;DR

This paper tackles the challenging problem of reconstructing sibling relationships within a population using genetic data. They introduce a novel optimization framework that uniquely combines statistical genetic concepts with combinatorial constraints derived from Mendelian inheritance laws, leading to a more robust and accurate sibling reconstruction method.

What Problem Does This Paper Address?

Identifying sibling relationships in a population is crucial for understanding various biological phenomena, from mating systems to evolutionary dynamics. This is particularly challenging when parental information is unknown, and researchers must rely solely on genetic markers. The "sibling reconstruction problem" (SRP) aims to group individuals into sibling families based on their genetic profiles. Existing methods often focus on either statistical likelihoods or combinatorial constraints, but rarely integrate both effectively. Furthermore, the "capacitated clustering problem" (CCP), a related problem in operations research, has been applied to SRP, but standard CCP formulations don't fully capture the complex, multi-dimensional genetic constraints of Mendelian inheritance. This paper addresses the need for a unified approach that leverages both the statistical information in genetic data and the biological rules of inheritance to achieve more accurate and reliable sibling reconstruction.

Methods

The authors propose a new Randomized Greedy Optimization Algorithm (RGOA) to solve the SRP. RGOA is inspired by the Greedy Randomized Adaptive Search Procedure (GRASP) and is divided into two main phases:

  • Construction Phase: This phase aims to generate diverse, high-quality feasible sibling groups. It modifies an existing approach (IMCS) by introducing a randomized weight perturbation to the individual weights. This perturbation encourages the exploration of a wider range of potential sibling group partitions. After generating multiple partitions, a Set Covering Problem (SCP) is solved to select the minimum set of sibling groups that cover all individuals, forming an initial solution.
  • Enhancement Phase: This phase focuses on improving the solution quality, specifically by maximizing the pairwise similarity between individuals within sibling groups. It employs a two-stage local search with a memory function (inspired by tabu search) to explore both cluster-based and individual-based neighborhoods. This helps refine the sibling groups and enhance their internal homogeneity. Finally, another SCP is solved to select the minimum set of sibling groups from the elite solutions generated.

The core of their approach lies in formulating the SRP as a Capacitated Clustering Problem (CCP-SRP) that integrates:

  • Statistical Similarity Measure: Used as the objective function to maximize the similarity within sibling groups.
  • Combinatorial Constraints: Derived from Mendel's laws, these constraints ensure the biological plausibility of the reconstructed sibling groups (e.g., allele inheritance rules).

Datasets

The authors evaluated their RGOA on several real biological datasets:

  • Salmon (Salmo salar): Atlantic salmon data.
  • Shrimp (Penaeus monodon): Tiger shrimp data.
  • Fly (Scaptodrosophila hibisci): Data from a generation of flies.
  • Ant (Leptothorax acervorum): Haplodiploid ant species data.
  • Turtle (Lepidochelys Kempi): Kemp's ridleys sea turtle data.

They also generated simulated datasets to test the algorithm's performance on larger and more complex scenarios.

Key Insights and Ideas

  • Unifying Statistical and Combinatorial Approaches: The most significant insight is the successful integration of statistical genetic information (similarity) with combinatorial biological rules (Mendel's laws) into a single optimization framework. This synergy leads to more biologically meaningful and accurate results.
  • Randomized Perturbation for Diversity: Introducing randomized perturbations in the construction phase is crucial for generating a diverse set of initial solutions, preventing the algorithm from getting stuck in local optima too early.
  • Two-Stage Local Search for Refinement: The enhancement phase's two-stage local search (cluster-based and individual-based) effectively improves solution quality by focusing on pairwise similarity, a key aspect of sibling relationships.
  • Robustness to Missing Data: The RGOA demonstrates improved robustness on datasets with a significant amount of missing genetic information, a common issue in real-world biological data.

Key Results

  • High Accuracy: RGOA achieved the highest reconstruction accuracies among all tested methods on most real biological datasets, often reaching 100% accuracy (e.g., on ant and shrimp datasets).
  • Outperformance: The proposed RGOA consistently outperformed other state-of-the-art methods, including 2AOM, IMCS, A&F, B&M, KINGROUP, and COLONY, especially on datasets with missing data.
  • Efficiency: While RGOA can be computationally demanding, it generally finds good feasible solutions within a reasonable time frame (under 20 hours), especially compared to methods that struggle with large datasets or missing information.
  • Robustness: The algorithm showed better performance on datasets with missing alleles and violations of Mendel's laws, suggesting its practical applicability.

Limitations and Future Work

  • Computational Time: The authors acknowledge that RGOA can be computationally intensive, particularly for complex problems. They suggest that future work could explore systematic frameworks like column generation to potentially improve efficiency.
  • Optimality Guarantee: As a heuristic method, RGOA does not guarantee an optimal solution. However, the focus is on achieving the most accurate solution, which may not always correspond to the mathematically optimal one in terms of statistical likelihood.
  • Data Errors: The current framework assumes error-free genetic data. Future work could investigate more robust optimization frameworks that can handle erroneous data.
  • Broader Applications: The authors suggest exploring new frameworks for half-sibling reconstruction and incorporating other biological objectives like minimizing parent pairs or inferring higher-ordered sibling relationships.

Summary updated

BibTeX
@article{chou2012capacitated,
  author = {Chun-An Chou and Wanpracha Art Chaovalitwongse and Tanya Y. Berger-Wolf and Bhaskar DasGupta and Mary V. Ashley},
  title = {{Capacitated clustering problem in computational biology: Combinatorial and statistical approach for sibling reconstruction}},
  journal = {Comput. Oper. Res.},
  year = {2012},
  doi = {10.1016/j.cor.2011.04.017},
}

Loading related content...

Figure