Restricted accessResearch articleFirst published online 2016-12
A Simple Approach to the Reconstruction of a Set of Points from the Multiset of n 2 Pairwise Distances in n 2 Steps for the Sequencing Problem: II. Algorithm
A new uniform algorithm based on sequential removal of redundancy from inputs is proposed to solve the turnpike and beltway problems. For error-free inputs that simulate experimental data with high accuracy, the size of inputs decreases from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$O ( {n^2} )$$
\end{document} to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$O ( n )$$
\end{document}, which permits one to eliminate exhaustive search almost completely and reconstruct sequences in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${n^2}$$
\end{document} steps. Computational experiments show high efficiency of the algorithm for both the turnpike and beltway cases, with the reconstruction time for sequences of lengths up to several thousand elements being within 1 second on a modern PC.
Get full access to this article
View all access options for this article.
References
1.
AllisonL., and YeeC.1988. Restriction site mapping is in separation theory. Comput. Appl. Biosci. 8, 97–101.
2.
AllmerJ.2011. Algorithms for the de novo sequencing of peptides from tandem mass spectra. Expert Rev. Proteomics, 8, 645–657.
3.
BandeiraN., NgJ., MeluzziD., et al.2008. De novo sequencing of nonribosomal peptides, 181–195. In Research in Computational Molecular Biology, volume 4955 of Lecture Notes in Computer Science Volume. Springer Berlin Heidelberg.
4.
BlazewiczJ., BurkeE., KasprzakM., et al.2007. The Simplified partial digest problem: Enumerative and dynamic programming algorithms. IEEE/ACM Trans. Comput. Biol. Bioinf. 4, 668–680.
5.
BlazewiczJ., BurkeE., KasprzakM., et al.2011. The Simplified Partial Digest Problem: Approximation and a graph-theoretic model. Eur. J. Operat. Res. 208, 142–152.
6.
BlazewiczJ., FormanowiczP., KasprzakM., et al.2001. Construction of DNA restriction maps based on a simplified experiment. Bioinformatics, 17, 398–404.
7.
ChenT., KaoM., TepelM., et al.2001. A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry. J. Comput. Biol. 8, 325–337.
8.
ChiH., SunR., YangB., et al.2010. pNovo: De novo peptide sequencing and identification using HCD spectra. J. Proteome Res. 9, 2713–2724.
9.
DakicT.2000. On the Turnpike problem [Ph.D. thesis]. Simon Fraser University. B.C., Canada.
10.
DixT., and KieronskaD.1988. Errors between sites in restriction site mapping. Comput. Appl. Biosci. 4, 117–123.
11.
FischerB., RothV., RoosF., et al.2005. NovoHMM: A hidden Markov model for de novo peptide sequencing. Anal. Chem. 77, 7265–7273.
12.
FitchW., SmithT., and RalphW.1983. Mapping the order of DNA restriction fragments. Gene, 22, 19–29.
13.
FominE.2015. Reconstruction of sequence from its circular partial sums for cyclopeptide sequencing problem. J. Bioinform. Comput. Biol. 13, 1540008.
14.
FrankA., and PevznerP.2005. PepNovo: De novo peptide sequencing via probabilistic network modeling. Anal. Chem. 77, 964–973.
15.
FrankA., SavitskiM., NielsenM., et al.2007. De novo peptide sequencing and identification with precision mass spectrometry. J. Proteome Res. 6, 114–123.
16.
GoldsteinL., and WatermanM.1987. Mapping DNA by stochastic relaxation. Adv. Appl. Math. 8, 194–207.
HoS., AllisonL., and YeeC.1990. Restriction site mapping for three or more enzymes. Comput. Appl. Biosci., 6, 195–204.
19.
InglehartJ., and NelsonP.1994. On the limitations of automated restriction mapping. Comput. Appl. Biosci. 10, 249–261.
20.
JohnsonR., and TaylorJ.2002. Searching sequence databases via de novo peptide sequencing by tandem mass spectrometry. Mol. Biotechnol. 22, 301–315.
21.
KrawczakM.1988. Algorithms for the restriction site mapping of DNA molecules. Proc. Natl. Acad. Sci. USA. 85, 7298–7301.
22.
LemkeP., SkienaS., and SmithW.2003. Reconstructing sets from interpoint distances. Discr. Comput. Geom. Alg. Comb. 25, 597–631.
23.
LemkeP., and WermanM.1988. On the complexity of inverting the autocorrelation function of a finite integer sequence, and the problem of locating n points on a line, given the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\left( {n \atop 2} \right)$$
\end{document} unlabelled distances between them. Technical Report 453, Institute for Mathematics and its Application IMA.
24.
LovaszL., and SchrijverA.1990. Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 1, 166–190.
25.
LuB., and ChenT.2003. A suboptimal algorithm for de novo peptide sequencing via tandem mass spectrometry. J. Comput. Biol. 10, 1–12.
26.
MaB., ZhangK., HendrieC., LiangC., LiM., Doherty-KirbyA., and LajoieG.2003. PEAKS: Powerful software for peptide de novo sequencing by tandem mass spectrometry. Rapid Commun. Mass Spectrom. 17, 2337–2342.
27.
MarraM., KucabaT., DietrichN., et al.1997. High throughput fingerprint analysis of large-insert clones. Genome Res. 7, 1072–1084.
28.
MoL., DuttaD., WanY., and ChenT.2007. MSNovo: A dynamic programming algorithm for de novo peptide sequencing via tandem mass spectrometry. Anal. Chem. 8, 325–337.
29.
NadimiR., FathabadiH., and GanjtabeshM.2011. A fast algorithm for the partial digest problem. Jpn. J. Indust. Appl. Math. 28, 315–325.
30.
NeilC., and PevznerP.2004. An Introduction to Bioinformatics Algorithms (Computational Molecular Biology). MIT Press, England.
31.
PevznerP.1995. DNA physical mapping and alternating Eulerian cycles in colored graphs. Algorithmica, 13, 77–105.
32.
PevznerP., DancikV., and TangC.2000. Mutation-tolerant protein identification by mass spectrometry. J. Comput. Biol. 7, 777–787.
33.
RosenblattJ., and SeymourP.1982. The structure of homometric sets. SIAM J. Algebra Discr. Methods, 3, 343–350.
34.
SakuraiT., MatsuoT., MatsudaH., et al.1984. PAAS 3: A computer program to determine probable sequence of peptides from mass spectrometric data. Biol. Mass Spectrom. 11, 396–399.
35.
ScigelovaM., HornshawM., GiannakopulosA., and MakarovA.2011. A. Fourier transform mass spectrometry. Mol. Cell. Proteom. 10, M111.009431–009M111.009431.
36.
SkienaS., SmithW., and LemkeP.1990. Reconstructing sets from interpoint distances, 332–339. In Proceedings of the Sixth ACM Symposium on Computational Geometry. Berkeley, CA. ACM, New York, NY.
37.
SkienaS., and SundaramG.1994. A partial digest approach to restriction site mapping. Bull. Math. Biol. 56, 275–294.
38.
Sur-KolayS., BanerjeeS., MukhopadhyayaS., et al.2005. Genetic algorithm for double digest problem, 623–629. In PalS., BandyopadhyayS., and BiswasS., eds., Pattern Recognition and Machine Intelligence, volume 3776 of Lecture Notes in Computer Science Volume. Springer Berlin Heidelberg.
39.
Sur-KolayS., BanerjeeS., MukhopadhyayaS., et al.2009. The double digest problem: Finding all solutions. Int. J. Bioinf. Res. Appl. 5, 570–592.
40.
TannerS., ShuH., FrankA., et al.2005. InsPecT: Identification of posttranslationally modified peptides from tandem mass spectra. Anal. Chem. 77, 4626–4639.
41.
WatermanM., and GriggsJ.1986. Interval graphs and maps of DNA. Bull. Math. Biol. 48, 189–195.
42.
WeissM.1994. Data Structures and Algorithm Analysis. The Benjamin/Cummings Publishing Company, Redwood City.
43.
WrightL., LichterJ., ReinitzJ., et al.1994. Computer-assisted restriction mapping: An integrated approach to handling experimental uncertainty. Comput. Appl. Biosci. 10, 435–442.
44.
ZhangZ.1982. An exponential example for a partial digest mapping algorithm. J. Comp. Biol. 1, 235–240.
45.
ZhangZ.2004. De novo peptide sequencing based on a divide-and-conquer algorithm and peptide tandem spectrum simulation. Anal. Chem. 76, 6374–6383.
