{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T00:15:38Z","timestamp":1719965738869},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,3,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Many comparative genomics studies rely on the correct identification of homologous genomic regions using accurate alignment tools. In such case, the alphabet of the input sequences consists of complete genes, rather than nucleotides or amino acids. As optimal multiple sequence alignment is computationally impractical, a progressive alignment strategy is often employed. However, such an approach is susceptible to the propagation of alignment errors in early pairwise alignment steps, especially when dealing with strongly diverged genomic regions. In this article, we present a novel accurate and efficient greedy, graph-based algorithm for the alignment of multiple homologous genomic segments, represented as ordered gene lists.<\/jats:p>\n               <jats:p>Results: Based on provable properties of the graph structure, several heuristics are developed to resolve local alignment conflicts that occur due to gene duplication and\/or rearrangement events on the different genomic segments. The performance of the algorithm is assessed by comparing the alignment results of homologous genomic segments in Arabidopsis thaliana to those obtained by using both a progressive alignment method and an earlier graph-based implementation. Especially for datasets that contain strongly diverged segments, the proposed method achieves a substantially higher alignment accuracy, and proves to be sufficiently fast for large datasets including a few dozens of eukaryotic genomes.<\/jats:p>\n               <jats:p>Availability: \u00a0http:\/\/bioinformatics.psb.ugent.be\/software. The algorithm is implemented as a part of the i-ADHoRe 3.0 package.<\/jats:p>\n               <jats:p>Contact: \u00a0yves.vandepeer@psb.vib-ugent.be<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btr008","type":"journal-article","created":{"date-parts":[[2011,1,8]],"date-time":"2011-01-08T01:26:38Z","timestamp":1294449998000},"page":"749-756","source":"Crossref","is-referenced-by-count":21,"title":["A greedy, graph-based algorithm for the alignment of multiple homologous gene lists"],"prefix":"10.1093","volume":"27","author":[{"given":"Jan","family":"Fostier","sequence":"first","affiliation":[{"name":"1 Department of Information Technology (INTEC), Gaston Crommenlaan 8, bus 201, Ghent University - IBBT, 2Department of Plant Systems Biology, VIB and 3Department of Plant Biotechnology and Genetics, Ghent University, Technologiepark 927, Ghent, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Proost","sequence":"additional","affiliation":[{"name":"1 Department of Information Technology (INTEC), Gaston Crommenlaan 8, bus 201, Ghent University - IBBT, 2Department of Plant Systems Biology, VIB and 3Department of Plant Biotechnology and Genetics, Ghent University, Technologiepark 927, Ghent, Belgium"},{"name":"1 Department of Information Technology (INTEC), Gaston Crommenlaan 8, bus 201, Ghent University - IBBT, 2Department of Plant Systems Biology, VIB and 3Department of Plant Biotechnology and Genetics, Ghent University, Technologiepark 927, Ghent, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bart","family":"Dhoedt","sequence":"additional","affiliation":[{"name":"1 Department of Information Technology (INTEC), Gaston Crommenlaan 8, bus 201, Ghent University - IBBT, 2Department of Plant Systems Biology, VIB and 3Department of Plant Biotechnology and Genetics, Ghent University, Technologiepark 927, Ghent, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yvan","family":"Saeys","sequence":"additional","affiliation":[{"name":"1 Department of Information Technology (INTEC), Gaston Crommenlaan 8, bus 201, Ghent University - IBBT, 2Department of Plant Systems Biology, VIB and 3Department of Plant Biotechnology and Genetics, Ghent University, Technologiepark 927, Ghent, Belgium"},{"name":"1 Department of Information Technology (INTEC), Gaston Crommenlaan 8, bus 201, Ghent University - IBBT, 2Department of Plant Systems Biology, VIB and 3Department of Plant Biotechnology and Genetics, Ghent University, Technologiepark 927, Ghent, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piet","family":"Demeester","sequence":"additional","affiliation":[{"name":"1 Department of Information Technology (INTEC), Gaston Crommenlaan 8, bus 201, Ghent University - IBBT, 2Department of Plant Systems Biology, VIB and 3Department of Plant Biotechnology and Genetics, Ghent University, Technologiepark 927, Ghent, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yves","family":"Van de Peer","sequence":"additional","affiliation":[{"name":"1 Department of Information Technology (INTEC), Gaston Crommenlaan 8, bus 201, Ghent University - IBBT, 2Department of Plant Systems Biology, VIB and 3Department of Plant Biotechnology and Genetics, Ghent University, Technologiepark 927, Ghent, Belgium"},{"name":"1 Department of Information Technology (INTEC), Gaston Crommenlaan 8, bus 201, Ghent University - IBBT, 2Department of Plant Systems Biology, VIB and 3Department of Plant Biotechnology and Genetics, Ghent University, Technologiepark 927, Ghent, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaas","family":"Vandepoele","sequence":"additional","affiliation":[{"name":"1 Department of Information Technology (INTEC), Gaston Crommenlaan 8, bus 201, Ghent University - IBBT, 2Department of Plant Systems Biology, VIB and 3Department of Plant Biotechnology and Genetics, Ghent University, Technologiepark 927, Ghent, Belgium"},{"name":"1 Department of Information Technology (INTEC), Gaston Crommenlaan 8, bus 201, Ghent University - IBBT, 2Department of Plant Systems Biology, VIB and 3Department of Plant Biotechnology and Genetics, Ghent University, Technologiepark 927, Ghent, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2011,1,6]]},"reference":[{"key":"2023012511540409400_B1","doi-asserted-by":"crossref","first-page":"2648","DOI":"10.1093\/bioinformatics\/btm389","article-title":"DNA reference alignment benchmarks based on tertiary structure of encoded proteins","volume":"23","author":"Carroll","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012511540409400_B2","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1093\/bioinformatics\/btq082","article-title":"A min-cut algorithm for the consistency problem in multiple sequence alignment","volume":"26","author":"Corel","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012511540409400_B3","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":"2023012511540409400_B4","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1109\/TIT.1956.1056816","article-title":"A note on the maximum flow through a network","volume":"2","author":"Elias","year":"1956","journal-title":"IRE Trans. Informat. Theory"},{"key":"2023012511540409400_B5","volume-title":"Flows in Networks.","author":"Ford","year":"1962"},{"key":"2023012511540409400_B6","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1016\/j.jtbi.2005.10.010","article-title":"Alignments of mitochondrial genome arrangements: Applications to metazoan phylogeny","volume":"240","author":"Fritzsch","year":"2006","journal-title":"J. Theor. Biol."},{"key":"2023012511540409400_B7","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0378-1119(88)90330-7","article-title":"Clustal: a package for performing multiple sequence alignment on a microcomputer","volume":"73","author":"Higgins","year":"1988","journal-title":"Gene"},{"issue":"Suppl. 1","key":"2023012511540409400_B8","doi-asserted-by":"crossref","first-page":"D690","DOI":"10.1093\/nar\/gkn828","article-title":"Ensembl 2009","volume":"37","author":"Hubbard","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023012511540409400_B9","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1038\/nature06148","article-title":"The grapevine genome sequence suggests ancestral hexaploidization in major angiosperm phyla","volume":"449","author":"Jaillon","year":"2007","journal-title":"Nature"},{"key":"2023012511540409400_B10","doi-asserted-by":"crossref","first-page":"3059","DOI":"10.1093\/nar\/gkf436","article-title":"Mafft: a novel method for rapid multiple sequence alignment based on fast fourier transform","volume":"30","author":"Katoh","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"2023012511540409400_B11","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1016\/j.tig.2008.08.009","article-title":"The quest for orthologs: finding the corresponding gene across genomes","volume":"24","author":"Kuzniar","year":"2008","journal-title":"Trends Genet. TIG"},{"key":"2023012511540409400_B12","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1093\/bioinformatics\/15.3.203","article-title":"An exact solution for the segment-to-segment multiple sequence alignment problem","volume":"15","author":"Lenhof","year":"1999","journal-title":"Bioinformatics"},{"key":"2023012511540409400_B13","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1093\/bioinformatics\/15.3.211","article-title":"Dialign 2: improvement of the segment-to-segment approach to multiple sequence alignment","volume":"15","author":"Morgenstern","year":"1999","journal-title":"Bioinformatics"},{"key":"2023012511540409400_B14","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol."},{"key":"2023012511540409400_B15","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1093\/bioinformatics\/14.5.407","article-title":"Coffee: an objective function for multiple sequence alignments","volume":"14","author":"Notredame","year":"1998","journal-title":"Bioinformatics"},{"key":"2023012511540409400_B16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","article-title":"T-coffee: a novel method for fast and accurate multiple sequence alignment","volume":"302","author":"Notredame","year":"2000","journal-title":"J. Mol. Biol."},{"key":"2023012511540409400_B17","doi-asserted-by":"crossref","first-page":"2509","DOI":"10.1093\/bioinformatics\/btq465","article-title":"DRIMM-Synteny: decomposing genomes into evolutionary conserved segments","volume":"26","author":"Pham","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012511540409400_B18","doi-asserted-by":"crossref","first-page":"445+","DOI":"10.1186\/1471-2105-11-445","article-title":"Automatic detection of anchor points for multiple sequence alignment","volume":"11","author":"Pitschi","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023012511540409400_B19","doi-asserted-by":"crossref","first-page":"47+","DOI":"10.1186\/1471-2105-4-47","article-title":"Oxbench: a benchmark for evaluation of protein multiple sequence alignment accuracy","volume":"4","author":"Raghava","year":"2003","journal-title":"BMC Bioinformatics"},{"key":"2023012511540409400_B20","doi-asserted-by":"crossref","first-page":"e8861+","DOI":"10.1371\/journal.pone.0008861","article-title":"CYNTENATOR: progressive gene order alignment of 17 vertebrate genomes","volume":"5","author":"R\u00f6delsperger","year":"2010","journal-title":"PloS One"},{"key":"2023012511540409400_B21","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1089\/cmb.1998.5.555","article-title":"Multiple genome rearrangement and breakpoint phylogeny","volume":"5","author":"Sankoff","year":"1998","journal-title":"J. Comput. Biol."},{"key":"2023012511540409400_B22","doi-asserted-by":"crossref","first-page":"5857","DOI":"10.1073\/pnas.95.11.5857","article-title":"Smart, a simple modular architecture research tool: Identification of signaling domains","volume":"95","author":"Schultz","year":"1998","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012511540409400_B23","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.1101\/gr.2179004","article-title":"Building genomic profiles for uncovering segmental homology in the twilight zone","volume":"14","author":"Simillion","year":"2004","journal-title":"Genome Res."},{"key":"2023012511540409400_B24","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1093\/bioinformatics\/btm449","article-title":"i-ADHoRe 2.0: an improved tool to detect degenerated genomic homology using genomic profiles","volume":"24","author":"Simillion","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012511540409400_B25","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of common molecular subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol."},{"key":"2023012511540409400_B26","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1126\/science.1153917","article-title":"Synteny and collinearity in plant genomes","volume":"320","author":"Tang","year":"2008","journal-title":"Science"},{"key":"2023012511540409400_B27","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1038\/35048692","article-title":"Analysis of the genome sequence of the flowering plant Arabidopsis thaliana","volume":"408","author":"The Arabidopsis Genome Initiative","year":"2000","journal-title":"Nature"},{"key":"2023012511540409400_B28","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","article-title":"Clustal w: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice","volume":"22","author":"Thompson","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"2023012511540409400_B29","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1002\/prot.20527","article-title":"Balibase 3.0: latest developments of the multiple sequence alignment benchmark","volume":"61","author":"Thompson","year":"2005","journal-title":"Proteins"},{"key":"2023012511540409400_B30","doi-asserted-by":"crossref","first-page":"1596","DOI":"10.1126\/science.1128691","article-title":"The genome of black cottonwood, populus trichocarpa (torr. & gray)","volume":"313","author":"Tuskan","year":"2006","journal-title":"Science"},{"key":"2023012511540409400_B31","doi-asserted-by":"crossref","first-page":"752","DOI":"10.1038\/nrg1449","article-title":"Computational approaches to unveiling ancient genome duplications","volume":"5","author":"Van de Peer","year":"2004","journal-title":"Nat. Rev. Genet."},{"key":"2023012511540409400_B32","doi-asserted-by":"crossref","first-page":"680","DOI":"10.1016\/j.tplants.2009.09.001","article-title":"The flowering world: a tale of duplications","volume":"14","author":"Van de Peer","year":"2009","journal-title":"Trends Plant Sci."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/6\/749\/48863509\/bioinformatics_27_6_749.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/6\/749\/48863509\/bioinformatics_27_6_749.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T12:02:54Z","timestamp":1674648174000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/6\/749\/234504"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,6]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,3,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btr008","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2011,3,15]]},"published":{"date-parts":[[2011,1,6]]}}}