Selecting An Unrelated Subset From Pairwise Estimates

From Pairwise Estimates to a Selection Problem

Pairwise kinship estimates identify pairs whose estimated relatedness exceeds a chosen threshold. If an analysis requires a set of samples with no such pair, the task is not to decide independently for each pair: removing one sample resolves every flagged pair that contains it. The task is to choose a set of samples that jointly satisfies the pairwise constraint.

This can be represented as a graph. Each sample is a vertex, and an edge joins two vertices when their pairwise estimate meets the prespecified threshold. A selected subset is acceptable if it contains no edge between any two selected samples. This graph formulation makes the constraint explicit, but it does not determine which acceptable subset is scientifically preferable.

Definition: Given a set of samples and a threshold \(\tau\), form an undirected graph \(G=(V,E)\). Each sample is a vertex \(i\in V\). For each pair \(i,j\), include the edge \((i,j)\in E\) if the prespecified pairwise kinship estimate \(\hat{\phi}_{ij}\) meets the chosen edge rule, here \(\hat{\phi}_{ij}\geq\tau\). An independent set is a subset \(S\subseteq V\) for which no two vertices in \(S\) are joined by an edge. A maximal independent set cannot be enlarged by adding another vertex from \(V\); a maximum independent set is an independent set with the largest possible number of vertices.

The edge rule must match the estimator and scientific aim. In the examples below, the estimate is a kinship coefficient on a kinship-coefficient scale, and an edge is present when the estimate is at least \(\tau\). A cutoff stated for another measure, such as an IBD-sharing estimate, cannot simply be substituted without accounting for its scale and interpretation. The threshold should be chosen and recorded before selection, rather than adjusted repeatedly to obtain a desired sample count.

A subset produced this way is operationally unrelated at the chosen threshold: no retained pair crosses the specified cutoff. It is not proof that the retained individuals have zero biological relatedness. Estimates are subject to uncertainty, and an edge rule converts continuous estimates into a binary decision. The thresholding material and pairwise diagnostics help inform this decision; the graph is a way to organize it.

Two Greedy Strategies

A greedy algorithm makes a sequence of locally defined choices rather than searching all possible subsets. Two common strategies are removal-based and retention-based. They can produce different valid subsets from the same graph.

Strategy	Choice at each step	What it guarantees
Degree-based removal	Remove a vertex with many currently incident edges; recompute degrees and continue until no edges remain.	The retained vertices form an independent set.
Priority-based retention	Consider vertices in a prespecified order; retain a vertex if it has no edge to an already retained vertex.	The retained set is independent and, if every vertex is considered, maximal.

The degree of a vertex is the number of its current edges. Recomputing degrees matters: after a sample is removed, its incident edges disappear, which may change which remaining sample has the highest degree. A priority order can be based on a predeclared scientific or data-quality rule, but it must be stated clearly. Examples include a preference for higher genotype call rate or a planned rule for retaining a designated group. Priorities are decisions about the analysis, not consequences of the graph itself.

Worked Example: Thresholding a Small Pairwise Table

Suppose five hypothetical samples have the following pairwise kinship estimates. Use \(\tau=0.050\) and include an edge when \(\hat{\phi}_{ij}\geq\tau\).

Pair	\(\hat{\phi}_{ij}\)	Edge?
A–B	0.090	Yes
A–C	0.070	Yes
B–C	0.060	Yes
C–D	0.080	Yes
D–E	0.055	Yes
A–D	0.020	No
A–E	0.010	No
B–D	0.030	No
B–E	0.025	No
C–E	0.015	No

The edge set is \(\{(A,B),(A,C),(B,C),(C,D),(D,E)\}\). The initial degrees are \(d_A=2\), \(d_B=2\), \(d_C=3\), \(d_D=2\), and \(d_E=1\), where \(d_i\) denotes the number of edges incident to sample \(i\).

For a degree-based removal rule, remove C first because it has the largest degree. The remaining edges are A–B and D–E. Suppose the prespecified tie-break is to remove the lower-call-rate sample among vertices tied for the largest current degree. If B has call rate 0.96 versus A's 0.99, remove B. If D has call rate 0.97 versus E's 0.98, remove D. The retained subset is then \(\{A,E\}\). It contains no edge, and the edge list shows why: A–E is below the threshold.

A different rule can produce a different answer. Consider priority-based retention in the order A, D, B, C, E. Retain A; then retain D because A–D is not an edge. B conflicts with A, C conflicts with both A and D, and E conflicts with D, so each is skipped. This rule retains \(\{A,D\}\), also an independent set of size two. The two subsets differ even though they were formed from the same estimates and threshold.

What Greedy Rules Guarantee—and What They Do Not

The basic guarantee is feasibility: a correctly implemented procedure returns a set with no internal edge. A retention-based procedure that considers every vertex also returns a maximal independent set. It does not generally return a maximum independent set. “Maximal” means that no single omitted vertex can be added to the chosen set; “maximum” compares the size of the chosen set with every independent set the graph could contain. These are different claims.

Justification: In priority-based retention, a vertex is retained only if it has no edge to an already retained vertex. Thus, when it is added, the set remains independent; skipping a vertex does not change that property. At the end, consider any skipped vertex \(v\). It was skipped because it had an edge to a vertex already retained at that step. Retained vertices are never removed, so that neighbor is still in the final set. Therefore, \(v\) cannot be added to the final set, and the set is maximal. This argument establishes maximality, not maximum size: it does not compare the set with other possible selections.

Worked Example: Maximal Does Not Mean Largest

Consider a hypothetical graph with one central sample H and four other samples L1, L2, L3, and L4. Suppose the only edges are H–L1, H–L2, H–L3, and H–L4. This could arise if each estimated kinship coefficient between H and an L sample is 0.060 at a threshold of \(\tau=0.050\), while every L–L estimate is 0.010.

If priority-based retention considers H first, it retains H and skips L1 through L4 because each has an edge to H. The result \(\{H\}\) is independent and maximal: no omitted L sample can be added while H remains. Its size is one.

If instead a degree-based rule removes H, it removes all four edges at once. The retained set \(\{L1,L2,L3,L4\}\) has no internal edges and has size four. In this graph it is a maximum independent set, because all four L samples can be retained together and any independent set containing H must exclude all four of them. This example shows that an acceptable greedy result need not retain as many samples as another acceptable result. It also shows why the priority or objective should be chosen deliberately.

Searching for a maximum independent set can be computationally demanding for large graphs; in general, it is an NP-hard optimization problem. A practical analysis often uses a transparent greedy rule rather than claiming to find a largest possible subset. If maximizing the number retained is an explicit requirement, the method should be described as an optimization procedure and its optimality should be established or its limitations reported. A greedy output alone does not establish optimality.

Choosing the Rule and Preserving the Decision

No single removal rule is best for every analysis. A degree-based rule can remove one highly connected sample to resolve several flagged pairs, but it does not account for sample quality or the scientific value of particular observations unless those features are incorporated explicitly. A priority-based rule makes such preferences visible, but the order can strongly affect the result. A rule that favors cases, for example, may be appropriate for a prespecified design goal, yet it can change the composition of the retained sample. The selected set should therefore be understood as a design decision, not as a uniquely dictated answer to the kinship estimates.

A reproducible record should let another analyst reconstruct both the graph and the choices made from it. Record at least:

the pairwise estimator and scale, and the exact edge rule, including whether equality at the threshold creates an edge;
the threshold value and the set of sample identifiers eligible for selection;
the algorithm, vertex priority or removal rule, and every tie-breaking rule;
the retained sample identifiers and the excluded identifiers, with the reason for each exclusion;
the input data or estimate-file version and any relevant processing choices that affect pairwise estimates.

It is useful to retain the thresholded edge list or an equivalent record of flagged pairs, not just the final sample list. The edge list allows checks that the output contains no flagged pair and helps explain why a sample was excluded. If several valid subsets are plausible, comparing them can reveal how the rule affects sample composition and sample count. The final choice should reflect the stated analysis objective and be documented before interpreting downstream results.

Worked Example: An Auditable Priority-Based Selection

Suppose a hypothetical analysis has four eligible samples, with threshold \(\tau=0.050\). Pairwise estimates are \(\hat{\phi}_{AB}=0.071\), \(\hat{\phi}_{BC}=0.063\), and \(\hat{\phi}_{CD}=0.058\); the other three pairwise estimates are below 0.050. The graph is the path A–B–C–D. Before selection, the analysis plan specifies the priority order A, C, B, D.

Start with an empty retained set. A is considered first and retained. C is not adjacent to A, so C is retained. B is adjacent to A and C, so B is excluded. D is adjacent to C, so D is excluded. The resulting set is \(\{A,C\}\). Its only pairwise estimate is below the threshold; suppose \(\hat{\phi}_{AC}=0.018\), so the retained set satisfies the edge rule.

A concise audit record would state: “Estimator: pairwise kinship coefficient; edge rule: \(\hat{\phi}_{ij}\geq0.050\); eligible samples: A, B, C, D; algorithm: priority-based retention; order: A, C, B, D; retained: A, C; excluded: B (edges to A and C), D (edge to C).” The estimate file or its version should also be recorded. This is enough to reproduce the selection without relying on memory about which pairs were flagged.

Common Mistakes and Practical Checks

Calling a greedy subset “the largest unrelated subset.” A greedy procedure can produce a maximal set without finding a maximum one. State only the guarantee the algorithm provides.
Treating the threshold as a universal biological boundary. The edge says that an estimate meets the specified rule; it does not prove a pair is related in an absolute sense, or that pairs below the threshold are exactly unrelated.
Changing rules without recording the change. Tie-breaking and priority order can change the retained samples. Specify them before applying the procedure and preserve the resulting decisions.
Checking only the number retained. A large subset is not sufficient evidence of success. Verify directly that no retained pair has an edge under the chosen rule.
Assuming exclusion is neutral. Removing samples can alter the composition of the analysis set. Report who was excluded and why, and consider whether the selection rule could systematically favor or disfavor a scientifically important group.

Key takeaway: Thresholded kinship estimates define a graph, and an acceptable unrelated analysis subset is an independent set in that graph. Greedy rules can produce transparent, valid subsets, but different rules can retain different samples, and maximality does not imply maximum size. Reproducibility requires recording the edge rule, threshold, algorithm, priorities, tie-breaks, retained samples, and exclusions.

Check Your Understanding

Answer each question using the definitions and procedures in this tutorial.

Under the edge rule \(\hat{\phi}_{ij}\geq\tau\), what does it mean for a selected subset to be independent?
Explain the difference between a maximal independent set and a maximum independent set.
In the central-vertex example, why does retaining H first produce a maximal set even though it is smaller than the set of four L samples?
Name two details, besides the threshold value, that should be recorded to reproduce a greedy selection.
Why should an edge be interpreted as a threshold-based decision rather than proof of a fixed biological relationship category?