{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:34:50Z","timestamp":1772138090634,"version":"3.50.1"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2018,7,2]],"date-time":"2018-07-02T00:00:00Z","timestamp":1530489600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Research Grant Council","award":["T12-402\/13N"],"award-info":[{"award-number":["T12-402\/13N"]}]},{"name":"RGC"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Cross-linking technique coupled with mass spectrometry (MS) is widely used in the analysis of protein structures and protein-protein interactions. In order to identify cross-linked peptides from MS data, we need to consider all pairwise combinations of peptides, which is computationally prohibitive when the sequence database is large. To alleviate this problem, some heuristic screening strategies are used to reduce the number of peptide pairs during the identification. However, heuristic screening strategies may miss some true cross-linked peptides.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We directly tackle the combination challenge without using any screening strategies. With the data structure of double-ended queue, the proposed algorithm reduces the quadratic time complexity of exhaustive searching down to the linear time complexity. We implement the algorithm in a tool named Xolik. The running time of Xolik is validated using databases with different numbers of proteins. Experiments using synthetic and empirical datasets show that Xolik outperforms existing tools in terms of running time and statistical power.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>Source code and binaries of Xolik are freely available at http:\/\/bioinformatics.ust.hk\/Xolik.html.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/bty526","type":"journal-article","created":{"date-parts":[[2018,6,28]],"date-time":"2018-06-28T23:10:31Z","timestamp":1530227431000},"page":"251-257","source":"Crossref","is-referenced-by-count":21,"title":["Xolik: finding cross-linked peptides with maximum paired scores in linear time"],"prefix":"10.1093","volume":"35","author":[{"given":"Jiaan","family":"Dai","sequence":"first","affiliation":[{"name":"Department of Electronic and Computer Engineering, The Hong Kong University of Science and Technology, Hong Kong, China"}]},{"given":"Wei","family":"Jiang","sequence":"additional","affiliation":[{"name":"Department of Electronic and Computer Engineering, The Hong Kong University of Science and Technology, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7695-3698","authenticated-orcid":false,"given":"Fengchao","family":"Yu","sequence":"additional","affiliation":[{"name":"Department of Electronic and Computer Engineering, The Hong Kong University of Science and Technology, Hong Kong, China"}]},{"given":"Weichuan","family":"Yu","sequence":"additional","affiliation":[{"name":"Department of Electronic and Computer Engineering, The Hong Kong University of Science and Technology, Hong Kong, China"}]}],"member":"286","published-online":{"date-parts":[[2018,7,2]]},"reference":[{"key":"2023013107231672200_bty526-B1","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1089\/106652701753307494","article-title":"Algorithms for identifying protein cross-links via tandem mass spectrometry","volume":"8","author":"Chen","year":"2001","journal-title":"J. Comput. Biol"},{"key":"2023013107231672200_bty526-B2","doi-asserted-by":"crossref","first-page":"923","DOI":"10.1021\/pr100848a","article-title":"Xlink-Identifier: an automated data analysis platform for confident identifications of chemically cross-linked peptides using tandem mass spectrometry","volume":"10","author":"Du","year":"2011","journal-title":"J. Proteome Res"},{"key":"2023013107231672200_bty526-B3","doi-asserted-by":"crossref","first-page":"976","DOI":"10.1016\/1044-0305(94)80016-2","article-title":"An approach to correlate tandem mass spectral data of peptides with amino acid sequences in a protein database","volume":"5","author":"Eng","year":"1994","journal-title":"J. Am. Soc. Mass Spectrom"},{"key":"2023013107231672200_bty526-B4","doi-asserted-by":"crossref","first-page":"4598","DOI":"10.1021\/pr800420s","article-title":"A fast SEQUEST cross correlation algorithm","volume":"7","author":"Eng","year":"2008","journal-title":"J. Proteome Res"},{"key":"2023013107231672200_bty526-B5","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1002\/pmic.201200439","article-title":"Comet: an open-source MS\/MS sequence database search tool","volume":"13","author":"Eng","year":"2013","journal-title":"Proteomics"},{"key":"2023013107231672200_bty526-B6","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/s13361-014-1001-1","article-title":"Automated assignment of MS\/MS cleavable cross-links in protein 3d-structure analysis","volume":"26","author":"G\u00f6tze","year":"2015","journal-title":"J. Am. Soc. Mass Spectrom"},{"key":"2023013107231672200_bty526-B7","doi-asserted-by":"crossref","first-page":"2190","DOI":"10.1021\/pr501321h","article-title":"Kojak: efficient analysis of chemically cross-linked protein complexes","volume":"14","author":"Hoopmann","year":"2015","journal-title":"J. Proteome Res"},{"key":"2023013107231672200_bty526-B8","doi-asserted-by":"crossref","first-page":"923","DOI":"10.1038\/nmeth1113","article-title":"Semi-supervised learning for peptide identification from shotgun proteomics datasets","volume":"4","author":"Kall","year":"2007","journal-title":"Nat. Methods"},{"key":"2023013107231672200_bty526-B9","doi-asserted-by":"crossref","first-page":"M110.002212.","DOI":"10.1074\/mcp.M110.002212","article-title":"Development of a novel cross-linking strategy for fast and accurate identification of cross-linked peptides of protein complexes","volume":"10","author":"Kao","year":"2011","journal-title":"Mol. Cell. Proteomics"},{"key":"2023013107231672200_bty526-B10","doi-asserted-by":"crossref","first-page":"3604","DOI":"10.1021\/pr200260n","article-title":"Structural analysis of a prokaryotic ribosome using a novel amidinating cross-linker and mass spectrometry","volume":"10","author":"Lauber","year":"2011","journal-title":"J. Proteome Res"},{"key":"2023013107231672200_bty526-B11","doi-asserted-by":"crossref","first-page":"1179","DOI":"10.1038\/nmeth.3603","article-title":"Proteome-wide profiling of protein assemblies by cross-linking mass spectrometry","volume":"12","author":"Liu","year":"2015","journal-title":"Nat. Methods"},{"key":"2023013107231672200_bty526-B12","doi-asserted-by":"crossref","first-page":"329.","DOI":"10.1038\/nmeth.3283","article-title":"Mapping native disulfide bonds at a proteome scale","volume":"12","author":"Lu","year":"2015","journal-title":"Nat. Methods"},{"key":"2023013107231672200_bty526-B13","doi-asserted-by":"crossref","first-page":"854","DOI":"10.1074\/mcp.M115.053082","article-title":"Cross-linking immunoprecipitation-MS (xIP-MS): topological analysis of chromatinassociated protein complexes using single affinity purification","volume":"15","author":"Makowski","year":"2016","journal-title":"Mol. Cell. Proteomics"},{"key":"2023013107231672200_bty526-B14","doi-asserted-by":"crossref","first-page":"2488","DOI":"10.1021\/pr901163d","article-title":"Detecting cross-linked peptides by searching against a database of cross-linked peptide pairs","volume":"9","author":"McIlwain","year":"2010","journal-title":"J. Proteome Res"},{"key":"2023013107231672200_bty526-B15","author":"Meng","year":"2017"},{"key":"2023013107231672200_bty526-B16","doi-asserted-by":"crossref","first-page":"6958","DOI":"10.1021\/ac101241t","article-title":"Cleavable cross-linker for protein structure analysis: reliable identification of cross-linking products by tandem MS","volume":"82","author":"M\u00fcLler","year":"2010","journal-title":"Anal. Chem"},{"key":"2023013107231672200_bty526-B17","doi-asserted-by":"crossref","first-page":"2508","DOI":"10.1021\/pr9011816","article-title":"xComb: a cross-linked peptide database approach to protein\u2013protein interaction analysis","volume":"9","author":"Panchaud","year":"2010","journal-title":"J. Proteome Res"},{"key":"2023013107231672200_bty526-B18","doi-asserted-by":"crossref","first-page":"3551","DOI":"10.1002\/(SICI)1522-2683(19991201)20:18<3551::AID-ELPS3551>3.0.CO;2-2","article-title":"Probability-based protein identification by searching sequence databases using mass spectrometry data","volume":"20","author":"Perkins","year":"1999","journal-title":"Electrophoresis"},{"key":"2023013107231672200_bty526-B19","doi-asserted-by":"crossref","first-page":"M110.001420.","DOI":"10.1074\/mcp.M110.001420","article-title":"An isotopically coded CID-cleavable biotinylated cross-linker for structural proteomics","volume":"10","author":"Petrotchenko","year":"2011","journal-title":"Mol. Cell. Proteomics"},{"key":"2023013107231672200_bty526-B20","doi-asserted-by":"crossref","first-page":"834","DOI":"10.1016\/S1044-0305(03)00327-1","article-title":"MS2Assign, automated assignment and nomenclature of tandem mass spectra of chemically crosslinked peptides","volume":"14","author":"Schilling","year":"2003","journal-title":"J. Am. Soc. Mass Spectrom"},{"key":"2023013107231672200_bty526-B21","doi-asserted-by":"crossref","first-page":"8799","DOI":"10.1021\/ac801646f","article-title":"Characterization of protein cross-links via mass spectrometry and an open-modification search strategy","volume":"80","author":"Singh","year":"2008","journal-title":"Anal. Chem"},{"key":"2023013107231672200_bty526-B22","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1074\/mcp.M113.034009","article-title":"Matching cross-linked peptide spectra: only as good as the worse identification","volume":"13","author":"Trnka","year":"2014","journal-title":"Mol. Cell. Proteomics"},{"key":"2023013107231672200_bty526-B23","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1038\/nmeth.2103","article-title":"False discovery rate estimation for cross-linked peptides identified by mass spectrometry","volume":"9","author":"Walzthoeni","year":"2012","journal-title":"Nat. Methods"},{"key":"2023013107231672200_bty526-B24","doi-asserted-by":"crossref","first-page":"1128","DOI":"10.1074\/mcp.M113.035758","article-title":"Combinatorial approach for large-scale identification of linked peptides from tandem mass spectrometry spectra","volume":"13","author":"Wang","year":"2014","journal-title":"Mol. Cell. Proteomics"},{"key":"2023013107231672200_bty526-B25","doi-asserted-by":"crossref","first-page":"904","DOI":"10.1038\/nmeth.2099","article-title":"Identification of cross-linked peptides from complex samples","volume":"9","author":"Yang","year":"2012","journal-title":"Nat. Methods"},{"key":"2023013107231672200_bty526-B26","doi-asserted-by":"crossref","first-page":"5802","DOI":"10.1073\/pnas.090099097","article-title":"High throughput protein fold identification by using experimental constraints derived from intramolecular cross-links and mass spectrometry","volume":"97","author":"Young","year":"2000","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023013107231672200_bty526-B27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s12859-016-1073-y","article-title":"ECL: an exhaustive search tool for the identification of cross-linked peptides using whole database","volume":"17","author":"Yu","year":"2016","journal-title":"BMC Bioinformatics"},{"key":"2023013107231672200_bty526-B28","doi-asserted-by":"crossref","first-page":"3942","DOI":"10.1021\/acs.jproteome.7b00338","article-title":"Exhaustively identifying cross-linked peptides with a linear computational complexity","volume":"16","author":"Yu","year":"2017","journal-title":"J. Proteome Res"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/2\/251\/48963380\/bioinformatics_35_2_251.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/2\/251\/48963380\/bioinformatics_35_2_251.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T05:08:53Z","timestamp":1675141733000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/35\/2\/251\/5047755"}},"subtitle":[],"editor":[{"given":"Oliver","family":"Stegle","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2018,7,2]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bty526","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/155069","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2019,1,15]]},"published":{"date-parts":[[2018,7,2]]}}}