Multi-Segment Reconstruction Using Invariant Features

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4629-4633
Number of pages5
ISBN (Print)9781538646588
DOIs
StatePublished - Sep 10 2018
Event2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018 - Calgary, Canada
Duration: Apr 15 2018Apr 20 2018

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume2018-April
ISSN (Print)1520-6149

Other

Other2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018
CountryCanada
CityCalgary
Period4/15/184/20/18

Fingerprint

DNA sequences
Recovery

Keywords

  • Cryo-EM
  • DNA sequence assembly
  • Invariant features
  • Multi-segment reconstruction
  • Non-convex optimization

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering

Cite this

Zehni, M., Do, M. N., & Zhao, Z. (2018). Multi-Segment Reconstruction Using Invariant Features. In 2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018 - Proceedings (pp. 4629-4633). [8461796] (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2018-April). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2018.8461796

Multi-Segment Reconstruction Using Invariant Features. / Zehni, Mona; Do, Minh N.; Zhao, Zhizhen.

2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2018. p. 4629-4633 8461796 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2018-April).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Zehni, M, Do, MN & Zhao, Z 2018, Multi-Segment Reconstruction Using Invariant Features. in 2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018 - Proceedings., 8461796, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, vol. 2018-April, Institute of Electrical and Electronics Engineers Inc., pp. 4629-4633, 2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018, Calgary, Canada, 4/15/18. https://doi.org/10.1109/ICASSP.2018.8461796
Zehni M, Do MN, Zhao Z. Multi-Segment Reconstruction Using Invariant Features. In 2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2018. p. 4629-4633. 8461796. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). https://doi.org/10.1109/ICASSP.2018.8461796
Zehni, Mona ; Do, Minh N. ; Zhao, Zhizhen. / Multi-Segment Reconstruction Using Invariant Features. 2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 4629-4633 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).
@inproceedings{2d4b7d2bf01e4281aca1d892857a0bbf,
title = "Multi-Segment Reconstruction Using Invariant Features",
abstract = "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.",
keywords = "Cryo-EM, DNA sequence assembly, Invariant features, Multi-segment reconstruction, Non-convex optimization",
author = "Mona Zehni and Do, {Minh N.} and Zhizhen Zhao",
year = "2018",
month = "9",
day = "10",
doi = "10.1109/ICASSP.2018.8461796",
language = "English (US)",
isbn = "9781538646588",
series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "4629--4633",
booktitle = "2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018 - Proceedings",
address = "United States",

}

TY - GEN

T1 - Multi-Segment Reconstruction Using Invariant Features

AU - Zehni, Mona

AU - Do, Minh N.

AU - Zhao, Zhizhen

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.

ER -