{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T19:08:12Z","timestamp":1770491292959,"version":"3.49.0"},"reference-count":27,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2020,3,14]],"date-time":"2020-03-14T00:00:00Z","timestamp":1584144000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,6,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Multiple sequence alignment (MSA) is important and challenging problem of computational biology. Most of the existing methods can only provide a short length multiple alignments in an acceptable time. Nevertheless, when the researchers confront the genome size in the multiple alignments, the process has required a huge processing space\/time. Accordingly, using the method that can align genome size rapidly and precisely has a great effect, especially on the analysis of the very long alignments. Herein, we have proposed an efficient method, called FAME, which vertically divides sequences from the places that they have common areas; then they are arranged in consecutive order. Then these common areas are shifted and placed under each other, and the subsequences between them are aligned using any existing MSA tool.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>The results demonstrate that the combination of FAME and the MSA methods and deploying minimizer are capable to be executed on personal computer and finely align long length sequences with much higher sum-of-pair (SP) score compared to the standalone MSA tools. As we select genomic datasets with longer length, the SP score of the combinatorial methods is gradually improved. The calculated computational complexity of methods supports the results in a way that combining FAME and the MSA tools leads to at least four times faster execution on the datasets.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>The source code and all datasets and run-parameters are accessible free on http:\/\/github.com\/naznoosh\/msa.<\/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\/btaa175","type":"journal-article","created":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T20:32:29Z","timestamp":1584045149000},"page":"3662-3668","source":"Crossref","is-referenced-by-count":13,"title":["FAME: fast and memory efficient multiple sequences alignment tool through compatible chain of roots"],"prefix":"10.1093","volume":"36","author":[{"given":"Etminan","family":"Naznooshsadat","sequence":"first","affiliation":[{"name":"Department of Computer Engineering , Shiraz Branch, Islamic Azad University, Shiraz, Iran"}]},{"given":"Parvinnia","family":"Elham","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering , Shiraz Branch, Islamic Azad University, Shiraz, Iran"}]},{"given":"Sharifi-Zarchi","family":"Ali","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering , Sharif University of Technology, Tehran, Iran"}]}],"member":"286","published-online":{"date-parts":[[2020,3,14]]},"reference":[{"key":"2023063010285682200_btaa175-B1","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1137\/0149012","article-title":"Trees, stars, and multiple biological sequence alignment","volume":"49","author":"Altschul","year":"1989","journal-title":"SIAM J. Appl. Math"},{"key":"2023063010285682200_btaa175-B2"},{"key":"2023063010285682200_btaa175-B3","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0022-2836(87)90316-0","article-title":"A strategy for the rapid multiple alignment of protein sequences: confidence levels from tertiary structure comparisons","volume":"198","author":"Barton","year":"1987","journal-title":"J. Mol. Biol"},{"key":"2023063010285682200_btaa175-B652422","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1186\/1471-2164-15-264","article-title":"Comparison of mapping algorithms used in high-throughput sequencing: application to Ion Torrent data","volume":"15","author":"Caboche","year":"2014","journal-title":"BMC Genomics"},{"key":"2023063010285682200_btaa175-B4","doi-asserted-by":"crossref","first-page":"33964","DOI":"10.1038\/srep33964","article-title":"FAMSA: fast and accurate multiple sequence alignment of huge protein families","volume":"6","author":"Deorowicz","year":"2016","journal-title":"Sci. Rep"},{"key":"2023063010285682200_btaa175-B5","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/j.jgg.2018.07.004","article-title":"VCSRA: a fast and accurate multiple sequence alignment algorithm with a high degree of parallelism","volume":"45","author":"Dong","year":"2018","journal-title":"J. Genet. Genom"},{"key":"2023063010285682200_btaa175-B6","doi-asserted-by":"crossref","first-page":"1792","DOI":"10.1093\/nar\/gkh340","article-title":"MUSCLE: multiple sequence alignment with high accuracy and high throughput","volume":"32","author":"Edgar","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023063010285682200_btaa175-B7","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02603120","article-title":"Progressive sequence alignment as a prerequisitetto correct phylogenetic trees","volume":"25","author":"Feng","year":"1987","journal-title":"J. Mol. Evol"},{"key":"2023063010285682200_btaa175-B8","doi-asserted-by":"crossref","first-page":"3826","DOI":"10.1093\/bioinformatics\/btw558","article-title":"MSAProbs-MPI: parallel multiple sequence aligner for distributed-memory systems","volume":"32","author":"Gonz\u00e1lez-Dom\u0131\u00b4nguez","year":"2016","journal-title":"Bioinformatics"},{"key":"2023063010285682200_btaa175-B9","author":"Khan","year":"2011"},{"key":"2023063010285682200_btaa175-B10","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"2023063010285682200_btaa175-B11","doi-asserted-by":"crossref","first-page":"1270","DOI":"10.1093\/bioinformatics\/18.9.1270","article-title":"Parallelized multiple alignment","volume":"18","author":"Kleinjung","year":"2002","journal-title":"Bioinformatics"},{"key":"2023063010285682200_btaa175-B12","doi-asserted-by":"crossref","first-page":"1501","DOI":"10.1006\/jmbi.1994.1104","article-title":"Hidden Markov models in computational biology: applications to protein modeling","volume":"235","author":"Krogh","year":"1994","journal-title":"J. Mol. Biol"},{"key":"2023063010285682200_btaa175-B13","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1093\/bioinformatics\/18.3.440","article-title":"PatternHunter: faster and more sensitive homology search","volume":"18","author":"Ma","year":"2002","journal-title":"Bioinformatics"},{"key":"2023063010285682200_btaa175-B14","first-page":"17"},{"key":"2023063010285682200_btaa175-B15","doi-asserted-by":"crossref","first-page":"3363","DOI":"10.1093\/bioinformatics\/bth408","article-title":"Reducing storage requirements for biological sequence comparison","volume":"20","author":"Roberts","year":"2004","journal-title":"Bioinformatics"},{"key":"2023063010285682200_btaa175-B16","author":"Salzberg","year":"2009"},{"key":"2023063010285682200_btaa175-B17","doi-asserted-by":"crossref","first-page":"ii189","DOI":"10.1093\/bioinformatics\/btg1077","article-title":"Divide-and-conquer multiple alignment with segment-based constraints","volume":"19","author":"Sammeth","year":"2003","journal-title":"Bioinformatics"},{"key":"2023063010285682200_btaa175-B18","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1038\/msb.2011.75","article-title":"Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega","volume":"7","author":"Sievers","year":"2011","journal-title":"Mol. Syst. Biol"},{"key":"2023063010285682200_btaa175-B19","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1002\/pro.3290","article-title":"Clustal Omega for making accurate alignments of many protein sequences","volume":"27","author":"Sievers","year":"2018","journal-title":"Protein Sci"},{"key":"2023063010285682200_btaa175-B20","author":"Stoye","year":"1997"},{"key":"2023063010285682200_btaa175-B21","doi-asserted-by":"crossref","first-page":"GC45","DOI":"10.1016\/S0378-1119(98)00097-3","article-title":"Multiple sequence alignment with the divide-and-conquer method","volume":"211","author":"Stoye","year":"1998","journal-title":"Gene"},{"key":"2023063010285682200_btaa175-B22","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/S0893-9659(97)00013-X","article-title":"Improving the divide-and-conquer approach to sum-of-pairs multiple sequence alignment","volume":"10","author":"Stoye","year":"1997","journal-title":"Appl. Math. Lett"},{"key":"2023063010285682200_btaa175-B23","doi-asserted-by":"crossref","first-page":"2682","DOI":"10.1093\/nar\/27.13.2682","article-title":"A comprehensive comparison of multiple sequence alignment programs","volume":"27","author":"Thompson","year":"1999","journal-title":"Nucleic Acids Res"},{"key":"2023063010285682200_btaa175-B24","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1186\/s13015-017-0116-x","article-title":"HAlign-II: efficient ultra-large multiple sequence alignment and phylogenetic tree reconstruction with distributed and parallel computing","volume":"12","author":"Wan","year":"2017","journal-title":"Algorithms Mol. Biol"},{"key":"2023063010285682200_btaa175-B25","doi-asserted-by":"crossref","first-page":"3011","DOI":"10.1093\/bioinformatics\/btx338","article-title":"M2Align: parallel multiple sequence alignment with a multi-objective metaheuristic","volume":"33","author":"Zambrano-Vega","year":"2017","journal-title":"Bioinformatics"},{"key":"2023063010285682200_btaa175-B26","doi-asserted-by":"crossref","first-page":"2475","DOI":"10.1093\/bioinformatics\/btv177","article-title":"HAlign: fast multiple similar DNA\/RNA sequence alignment based on the centre star strategy","volume":"31","author":"Zou","year":"2015","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaa175\/33294382\/btaa175.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/12\/3662\/50749076\/bioinformatics_36_12_3662.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/12\/3662\/50749076\/bioinformatics_36_12_3662.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T10:29:20Z","timestamp":1688120960000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/12\/3662\/5805384"}},"subtitle":[],"editor":[{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2020,3,14]]},"references-count":27,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2020,6,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa175","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,6,15]]},"published":{"date-parts":[[2020,3,14]]}}}