TY - GEN
T1 - Multi-Segment Reconstruction Using Invariant Features
AU - Zehni, Mona
AU - Do, Minh N.
AU - Zhao, Zhizhen
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/9/10
Y1 - 2018/9/10
N2 - Multi-segment reconstruction (MSR) problem consists of recovering a signal from noisy segments with unknown positions of the observation windows. One example arises in DNA sequence assembly, which is typically solved by matching short reads to form longer sequences. Instead of trying to locate the segment within the sequence through pair-wise matching, we propose a new approach that uses shift-invariant features to estimate both the underlying signal and the distribution of the positions of the segments. Using the invariant features, we formulate the problem as a constrained nonlinear least-squares. The non-convexity of the problem leads to its sensitivity to the initialization. However, with clean data, we show empirically that for longer segment lengths, random initialization achieves exact recovery. Furthermore, we compare the performance of our approach to the results of expectation maximization and demonstrate that the new approach is robust to noise and computationally more efficient.
AB - Multi-segment reconstruction (MSR) problem consists of recovering a signal from noisy segments with unknown positions of the observation windows. One example arises in DNA sequence assembly, which is typically solved by matching short reads to form longer sequences. Instead of trying to locate the segment within the sequence through pair-wise matching, we propose a new approach that uses shift-invariant features to estimate both the underlying signal and the distribution of the positions of the segments. Using the invariant features, we formulate the problem as a constrained nonlinear least-squares. The non-convexity of the problem leads to its sensitivity to the initialization. However, with clean data, we show empirically that for longer segment lengths, random initialization achieves exact recovery. Furthermore, we compare the performance of our approach to the results of expectation maximization and demonstrate that the new approach is robust to noise and computationally more efficient.
KW - Cryo-EM
KW - DNA sequence assembly
KW - Invariant features
KW - Multi-segment reconstruction
KW - Non-convex optimization
UR - http://www.scopus.com/inward/record.url?scp=85054284645&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85054284645&partnerID=8YFLogxK
U2 - 10.1109/ICASSP.2018.8461796
DO - 10.1109/ICASSP.2018.8461796
M3 - Conference contribution
AN - SCOPUS:85054284645
SN - 9781538646588
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 4629
EP - 4633
BT - 2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018
Y2 - 15 April 2018 through 20 April 2018
ER -