{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T22:14:45Z","timestamp":1775168085892,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2007,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>In general, the construction of trees is based on sequence alignments. This procedure, however, leads to loss of informationwhen parts of sequence alignments (for instance ambiguous regions) are deleted before tree building. To overcome this difficulty, one of us previously introduced a new and rapid algorithm that calculates dissimilarity matrices between sequences without preliminary alignment.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>In this paper, HIV (Human Immunodeficiency Virus) and SIV (Simian Immunodeficiency Virus) sequence data are used to evaluate this method. The program produces tree topologies that are identical to those obtained by a combination of standard methods detailed in the HIV Sequence Compendium. Manual alignment editing is not necessary at any stage. Furthermore, only one user-specified parameter is needed for constructing trees.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>The extensive tests on HIV\/SIV subtyping showed that the virus classifications produced by our method are in good agreement with our best taxonomic knowledge, even in non-coding LTR (Long Terminal Repeat) regions that are not tractable by regular alignment methods due to frequent duplications\/insertions\/deletions. Our method, however, is not limited to the HIV\/SIV subtyping. It provides an alternative tree construction without a time-consuming aligning procedure.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-8-1","type":"journal-article","created":{"date-parts":[[2007,1,2]],"date-time":"2007-01-02T14:13:51Z","timestamp":1167747231000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":302,"title":["Comparing sequences without using alignments: application to HIV\/SIV subtyping"],"prefix":"10.1186","volume":"8","author":[{"given":"Gilles","family":"Didier","sequence":"first","affiliation":[]},{"given":"Laurent","family":"Debomy","sequence":"additional","affiliation":[]},{"given":"Maude","family":"Pupin","sequence":"additional","affiliation":[]},{"given":"Ming","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Grossmann","sequence":"additional","affiliation":[]},{"given":"Claudine","family":"Devauchelle","sequence":"additional","affiliation":[]},{"given":"Ivan","family":"Laprevotte","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,1,2]]},"reference":[{"key":"1373_CR1","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1093\/bioinformatics\/18.3.452","volume":"18","author":"C Lee","year":"2002","unstructured":"Lee C, Grasso C, Sharlow MF: Multiple sequence alignment using partial order graphs. Bioinformatics 2002, 18: 452\u2013464. 10.1093\/bioinformatics\/18.3.452","journal-title":"Bioinformatics"},{"key":"1373_CR2","doi-asserted-by":"publisher","first-page":"1546","DOI":"10.1093\/bioinformatics\/bth126","volume":"20","author":"C Grasso","year":"2004","unstructured":"Grasso C, Lee C: Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems. Bioinformatics 2004, 20: 1546\u20131556. 10.1093\/bioinformatics\/bth126","journal-title":"Bioinformatics"},{"key":"1373_CR3","doi-asserted-by":"publisher","first-page":"2336","DOI":"10.1101\/gr.2657504","volume":"14","author":"B Raphael","year":"2004","unstructured":"Raphael B, Zhi D, Tang H, Pevzner P: A novel method for multiple alignment of sequences with repeated and shuffled elements. Genome Res 2004, 14: 2336\u20132346. 10.1101\/gr.2657504","journal-title":"Genome Res"},{"key":"1373_CR4","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/PL00006138","volume":"44","author":"I Laprevotte","year":"1997","unstructured":"Laprevotte I, Brouillet S, Terzian C, H\u00e9naut A: Retroviral oligonucleotide distributions correlate with biased nucleotide compositions of retrovirus sequences, suggesting a duplicative stepwise molecular evolution. J Mol Evol 1997, 44: 214\u2013225. 10.1007\/PL00006138","journal-title":"J Mol Evol"},{"key":"1373_CR5","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.1093\/oxfordjournals.molbev.a003909","volume":"18","author":"I Laprevotte","year":"2001","unstructured":"Laprevotte I, Pupin M, Coward E, Didier G, Terzian C, Devauchelle C, H\u00e9naut A: HIV-1 and HIV-2 LTR nucleotide sequences: assessment of the alignment by N-block presentation, \u00abretroviral signatures\u00bb of overrepeated oligonucleotides, and a probable important role of scrambled stepwise duplications\/deletions in molecular evolution. Mol Biol Evol 2001, 18: 1231\u20131245.","journal-title":"Mol Biol Evol"},{"key":"1373_CR6","doi-asserted-by":"publisher","first-page":"12832","DOI":"10.1073\/pnas.91.26.12832","volume":"91","author":"S Karlin","year":"1994","unstructured":"Karlin S, Ladunga I: Comparisons of eukaryotic genomic sequences. Proc Natl Acad Sci USA 1994, 91: 12832\u201312836. 10.1073\/pnas.91.26.12832","journal-title":"Proc Natl Acad Sci USA"},{"key":"1373_CR7","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0304-3975(97)00122-9","volume":"215","author":"G Didier","year":"1999","unstructured":"Didier G: Caract\u00e9risation des N -\u00e9critures et application \u00e0 l'\u00e9tude des suites de complexit\u00e9 ultimement n + cste . Theor Comput Sc 1999, 215: 31\u201349. 10.1016\/S0304-3975(97)00122-9","journal-title":"Theor Comput Sc"},{"key":"1373_CR8","doi-asserted-by":"publisher","first-page":"1465","DOI":"10.1089\/cmb.2006.13.1465","volume":"13","author":"G Didier","year":"2006","unstructured":"Didier G, Laprevotte I, Pupin M, H\u00e9naut A: Local decoding of sequences and alignment-free comparison. J Comput Biol 2006, 13: 1465\u20131476. 10.1089\/cmb.2006.13.1465","journal-title":"J Comput Biol"},{"key":"1373_CR9","volume-title":"An overview of the molecular phylogeny of lentiviruses","author":"BT Foley","year":"2000","unstructured":"Foley BT: An overview of the molecular phylogeny of lentiviruses.2000. [http:\/\/www.hiv.lanl.gov\/content\/hiv-db\/REVIEWS\/reviews.html]"},{"key":"1373_CR10","first-page":"27","volume-title":"Computational and Evolutionary Analysis of HIV Molecular Sequences","author":"CL Kuiken","year":"2001","unstructured":"Kuiken CL, Leitner T: HIV-1 Subtyping. In Computational and Evolutionary Analysis of HIV Molecular Sequences. Edited by: Rodrigo AG, Learn GH. Jr. Kluwer Academic Publishers; 2001:27\u201353."},{"key":"1373_CR11","volume-title":"HIV-1 Nomenclature Proposal (a reference guide to HIV-1 classification)","author":"DL Robertson","year":"1999","unstructured":"Robertson DL, Anderson JP, Bradac JA, Carr JK, Foley B, Funkhouser RK, Gao F, Hahn BH, Kalish ML, Kuiken C, Learn GH, Leitner T, McCutchan F, Osmanov S, Peeters M, Pieniazek D, Salminen M, Sharp PM, Wolinsky S, Korber B: HIV-1 Nomenclature Proposal (a reference guide to HIV-1 classification).1999. [http:\/\/www.hiv.lanl.gov\/content\/hiv-db\/REVIEWS\/reviews.html]"},{"key":"1373_CR12","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1038\/17130","volume":"397","author":"F Gao","year":"1999","unstructured":"Gao F, Bailes E, Robertson DL, Chen Y, Rodenburg CM, Michael SF, Cummins LB, Arthur LO, Peeters M, Shaw GM, Sharp PM, Hahn BH: Origin of HIV-1 in the chimpanzee Pan troglodytes troglodytes. Nature 1999, 397: 436\u2013441. 10.1038\/17130","journal-title":"Nature"},{"key":"1373_CR13","unstructured":"Leitner T, Foley B, Hahn B, Marx P, McCutchan F, Mellors J, Wolinsky S, Korber B (Eds): HIV Sequence Compendium In Theoretical Biology and Biophysics Group, Los Alamos National Laboratory, LA-URnumber 04\u20137420 2003."},{"key":"1373_CR14","volume-title":"Recombinant HIV Sequences: Their Role in the Global Epidemic","author":"M Peeters","year":"2000","unstructured":"Peeters M: Recombinant HIV Sequences: Their Role in the Global Epidemic.2000. [http:\/\/www.hiv.lanl.gov\/content\/hiv-db\/REVIEWS\/reviews.html]"},{"key":"1373_CR15","volume-title":"Diversity and Evolution of Primate Lentiviruses","author":"BE Beer","year":"1999","unstructured":"Beer BE, Bailes E, Sharp PM, Hirsch VM: Diversity and Evolution of Primate Lentiviruses.1999. [http:\/\/www.hiv.lanl.gov\/content\/hiv-db\/REVIEWS\/reviews.html]"},{"key":"1373_CR16","unstructured":"Comparing sequences without using alignment scores[http:\/\/iml.univ-mrs.fr\/~didier\/laprevot\/]"},{"key":"1373_CR17","unstructured":"HIV-1\/HIV-2\/SIV Complete Genomes[http:\/\/www.hiv.lanl.gov\/content\/hiv-db\/COMPENDIUM\/2000\/HIV12SIVcomplete.pdf]"},{"key":"1373_CR18","doi-asserted-by":"publisher","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","volume":"22","author":"JD Thompson","year":"1994","unstructured":"Thompson JD, Higgins DG, Gibson TJ: CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res 1994, 22: 4673\u20134680. 10.1093\/nar\/22.22.4673","journal-title":"Nucleic Acids Res"},{"key":"1373_CR19","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1093\/bioinformatics\/15.3.211","volume":"15","author":"B Morgenstern","year":"1999","unstructured":"Morgenstern B: DIALIGN 2: improvement of the segment-to-segment approach to multiple sequence alignment. Bioinformatics 1999, 15: 211\u2013218. 10.1093\/bioinformatics\/15.3.211","journal-title":"Bioinformatics"},{"key":"1373_CR20","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1093\/bioinformatics\/14.9.755","volume":"14","author":"SR Eddy","year":"1998","unstructured":"Eddy SR: Profile Hidden Markov Models. Bioinformatics 1998, 14: 755\u2013763. 10.1093\/bioinformatics\/14.9.755","journal-title":"Bioinformatics"},{"key":"1373_CR21","unstructured":"HMMER[http:\/\/hmmer.janelia.org\/]"},{"key":"1373_CR22","unstructured":"The 2000 HIV Sequence Compendium[http:\/\/www.hiv.lanl.gov\/content\/hiv-db\/HTML\/compendium.html]"},{"key":"1373_CR23","unstructured":"HIV-1 Nomenclature Proposal[http:\/\/hiv-web.lanl.gov\/content\/hiv-db\/REVIEWS\/nomenclature\/Nomen.html]"},{"key":"1373_CR24","unstructured":"Los Alamos HIV sequence database[http:\/\/hiv-web.lanl.gov\/]"},{"key":"1373_CR25","volume-title":"Distributed by the author. Department of Genome Sciences","author":"J Felsenstein","year":"2005","unstructured":"Felsenstein J: PHYLIP (Phylogeny Inference Package) version 3.6. In Distributed by the author. Department of Genome Sciences. University of Washington, Seattle; 2005."},{"key":"1373_CR26","doi-asserted-by":"publisher","first-page":"783","DOI":"10.2307\/2408678","volume":"39","author":"J Felsenstein","year":"1985","unstructured":"Felsenstein J: Confidence intervals on phylogenies: an approach using the bootstrap. Evolution 1985, 39: 783\u2013791. 10.2307\/2408678","journal-title":"Evolution"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-8-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T21:40:57Z","timestamp":1630446057000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-8-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1,2]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,12]]}},"alternative-id":["1373"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-8-1","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1,2]]},"assertion":[{"value":"26 July 2006","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 January 2007","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 January 2007","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"1"}}