In this paper, we investigate the sequence estimation problem of faster-than-Nyquist (FTN) signaling as a promising approach for increasing spectral efficiency (SE) in future communication systems. In doing so, we exploit the concept of Gaussian separability and propose two probabilistic data association (PDA) algorithms with polynomial time complexity to detect binary phase-shift keying (BPSK) FTN signaling. Simulation results show that the proposed PDA algorithm outperforms the recently proposed SSSSE and SSSgb$K$SE algorithms for all SE values with a modest increase in complexity. The PDA algorithm approaches the performance of the semidefinite relaxation (SDRSE) algorithm for SE values of $0.96$ bits/sec/Hz, and it is within the $0.5$ dB signal-to-noise ratio (SNR) penalty at SE values of $1.10$ bits/sec/Hz for the fixed values of $beta = 0.3$.