.png){kind=icon}
.png){kind=icon}
Return
Multi-Bit Decision-Based Bitwise Majority Alignment Algorithm for Trace Reconstruction
.png){kind=icon}
PRE
AI
DOI：10.1109/LCOMM.2025.3648494.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
To recover the sequence $\boldsymbol {x}$ from several noisy traces of $\boldsymbol {x}$ corrupted by random deletions, the bitwise majority alignment (BMA) algorithm reconstructs each bit sequentially by taking a majority vote on its value in all traces. For each bit, only one bit in each trace is used to make a decision in BMA, and the correlation with its neighbors is ignored. In this letter, we develop a novel multi-bit decision-based BMA (MBD-BMA) for trace reconstruction. The proposed MBD-BMA uses multiple subsequent bits from each trace to reconstruct a bit of $\boldsymbol {x}$ more precisely than BMA. The main idea of MBD-BMA is to use a binary tree to represent all possible cases of the subsequent bits for the bit to be reconstructed, with a weight assigned to each case, i.e., each branch of the binary tree. The bit is then reconstructed by using the minimum-weight branch. Simulation results show that the Levenshtein error rate of the proposed MBD-BMA is significantly lower than that of BMA, while the increased complexity of MBD-BMA is relatively low.
Keywords:
Bitwise majority alignment (BMA)
deletions
DNA storage
multi-bit decision
trace reconstruction