Project Overview

As a sequencing company, we frequently received client-provided index information for post-sequencing sample demultiplexing. However, these indexes were often problematic. Indexes from different samples within the same lane could be highly similar or even duplicated, leading to demultiplexing failures or reduced confidence in sample assignment. Previously, we manually inspected indexes to avoid duplication and used conservative demultiplexing parameters that allowed only minimal index mismatches. However, this approach became increasingly labor-intensive when processing multiple lanes containing samples from different clients. The situation was further complicated by index information being transferred through sales teams, where errors could occur during communication or data handling. To address this issue, I designed an algorithm to:

  1. Automatically detect duplicated or highly similar sample indexes, reducing index-related errors to ~0% and improving inspection efficiency by ~98%.
  2. Determine the maximum safe mismatch allowance between indexes, improving demultiplexing yield by ~2%.

Version 1

The first version of the algorithm was designed to calculate the distance between every pair of index sequences.

  • Assumption: Index mismatch is only allowed for ONE of the paired index.

Goal

maximum safe mismatch allowance (MSMA) → How many mismatches can be allowed before one index becomes indistinguishable from another exact index sequence？

Case 1: Indexes with the same length

seq1: ATGGC
seq2: AGCGC

To convert seq1 into seq2, two positions need to be changed:

seq1: ATGGC
seq2: AGCGC
       ^ ^

Therefore, the distance between seq1 and seq2 is 2 mismatches. For seq1, this means that allowing 1 mismatch would still prevent it from becoming exactly identical to seq2. In other words:

MSMA = distance - 1 = 2 - 1
                    = 1

MSMA = 1

Case 2: Indexes with different lengths

If two index sequences have different lengths:

seq1: AGT
seq2: AGCGC

To compare them, the algorithm pads seq1 with N in all possible positions until it has the same length as seq2 ：

seq1-1: NNAGT
seq1-2: NAGTN
seq1-3: AGTNN

seq2:   AGCGC

Each padded version is then compared with seq2.

seq1-1: NNAGT
seq2:   AGCGC

-> requires 4 mismatches to become seq2

seq1-2: NAGTN
seq2:   AGCGC

-> requires 5 mismatches to become seq2

seq1-3: AGTNN
seq2:   AGCGC

-> requires 3 mismatches to become seq2

minimum padded distance = 3 However, because 2 artificial N bases were inserted, these positions should not be counted as real mismatches from the original index sequence.

adjusted distance = minimum padded distance - number of inserted N bases
                  = 3 - 2
                  = 1
MSMA = adjusted distance - 1 = 1 - 1
                             = 0

Version 2: Symmetric Mismatch Collision Detection

Goal

The first version of the algorithm had one important limitation: it assumed that only one index sequence could contain mismatches. The problem is that seq2 can also contain mismatches during demultiplexing. This means that seq1 and seq2 do not need to become each other directly. Instead, they only need to become the same intermediate sequence.

seq1: ATGGC
seq2: AGCGC

A possible intermediate sequence is:

collision sequence: AGGGC

Then

seq1: ATGGC
      AGGGC
       ^
      1 mismatch

seq2: AGCGC
      AGGGC
        ^
      1 mismatch

Therefore the formula in version 1 IS NOT ALWAYS TRUE

MSMA = adjusted distance - 1

New Concept: Collision Sequence

  • A collision sequence is an intermediate sequence that both indexes could become after mismatches.
x = number of mismatches required for seq1 to become the collision sequence
y = number of mismatches required for seq2 to become the collision sequence

Goal

The goal is to find the collision sequence where x and y are as balanced as possible：

minimum abs(x - y)

If two index sequences differ by d positions, then the minimum collision condition is:

seq1 needs floor(d / 2) mismatches
seq2 needs ceil(d / 2) mismatches

or vice versa.

EXAMPLE

If the two indexes differ by 4 positions

d = 4

The closest collision condition is:

seq1: 2 mismatches
seq2: 2 mismatches

So if both indexes are allowed 2 mismatches, they may collide. If the two indexes differ by 5 positions The closest collision condition is:

seq1: 2 mismatches
seq2: 3 mismatches

or

seq1: 3 mismatches
seq2: 2 mismatches

So if both indexes are allowed 3 mismatches, they may collide. **MSMA is **

MSMA = floor((d - 1) / 2)

EXAMPLE

seq1: ATGGC
seq2: AGCGC

so:

d = 2

therefore

MSMA = floor((2 - 1) / 2)
		 = floor(0.5) 
		 = 0

→ allowing 1 mismatch is already unsafe, because both indexes could mutate toward the same collision sequence. if 1 mismatch, seq1 can be AGGGC, seq2 can be AGGGC *(red is mismatched) → *same collision sequence.

Handling Indexes with Different Lengths

If seq1 is shorter than seq2, for example:

seq1: AGT
seq2: AGCGC

The algorithm pads the shorter sequence with N in all possible positions until both sequences have the same length.

seq1-1: NNAGT
seq1-2: NAGTN
seq1-3: AGTNN

seq2:   AGCGC

Each padded version of seq1 is then compared against seq2.

seq1-1: NNAGT
seq2:   AGCGC
adjusted distance = total differences - inserted N bases = 2

and

seq1-2: NAGTN
seq2:   AGCGC
adjusted distance = total differences - inserted N bases = 3

and

seq1-3: AGTNN
seq2:   AGCGC
adjusted distance = total differences - inserted N bases = 1

The algorithm takes the smallest adjusted distance, because this represents the most dangerous case

MSMA = floor((1 - 1) / 2) = 0

→ no mismatch should be allowed

Calculating MSMA Across Multiple Samples

  • In real sequencing runs, each lane usually contains multiple samples.
Sample_ID,Index
SampleA,ATGGC
SampleB,AGCGC
SampleC,TTAAC
SampleD,ATGGA

Pairwise comparison within each lane

SampleA vs SampleB = 2
SampleA vs SampleC = 3
SampleA vs SampleD = 1

minimum distance for SampleA = 1 This means SampleD is the closest index to SampleA. Even though SampleA is far away from SampleC, that does not matter for safety. The mismatch allowance must be determined by the closest possible collision.

MSMA_sampleA = 1 - 1 = 0

No mismatch is allowed for SampleA.

Additional Edge Cases and Data Validation Rules

In this workflow, Index1 is always expected to exist, while Index2 may be empty. Therefore, the algorithm needs to handle missing Index2 values carefully to avoid false safety assumptions or incorrect distance calculations.

Case 1: Duplicated Index1 with missing Index2

Sample_ID,Index,Index2
SampleA,ATGGC,
SampleB,ATGGC,

→ 2 samples cannot be distinguished during demultiplexing BUT, duplicated Index1 is not necessarily fatal if Index2 is available and different. For example:

Sample_ID,Index,Index2
SampleA,ATGGC,TTAAC
SampleB,ATGGC,CCGTA

Case 2: Missing Index2 should not be included in Index2 distance calculation

  • when some samples have Index2, while others do not…
Sample_ID,Index,Index2
SampleA,ATGGC,TTAAC
SampleB,CGTAA,

algorithm should skip

TTAAC vs `empty`

Limitation of Version 2

  • We only consider shift-style padding, not all possible N insertion positions:

    NNAGT
NAGTN
AGTNN

    NOT

NANGT
NAGNT
ANNGT
ANGNT
AGNTN
...
  • Assume index1 will never be empty.
← Back to projects