{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,6]],"date-time":"2024-06-06T22:41:40Z","timestamp":1717713700591},"reference-count":0,"publisher":"Oxford University Press (OUP)","issue":"16","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004,11,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: This paper is concerned with algorithms for aligning two whole genomes so as to identify regions that possibly contain conserved genes. Motivated by existing heuristic-based software tools, we initiate the study of an optimization problem that attempts to uncover conserved genes with a global concern. Another interesting feature in our formulation is the tolerance of noise, which also complicates the optimization problem. A brute-force approach takes time exponential in the noise level.<\/jats:p>\n               <jats:p>Results: We show how an insight into the optimization structure can lead to a drastic improvement in the time and space requirement [precisely, to O(k2n2) and O(k2n), respectively, where n is the size of the input and k is the noise level]. The reduced space requirement allows us to implement the new algorithm, called MaxMinCluster, on a PC. It is exciting to see that when tested with different real data sets, MaxMinCluster consistently uncovers a high percentage of conserved genes that have been published by GenBank. Its performance is indeed favorably compared to MUMmer (perhaps the most popular software tool for uncovering conserved genes in a whole-genome scale).<\/jats:p>\n               <jats:p>Availability: The source code is available from the website http:\/\/www.csis.hku.hk\/~colly\/maxmincluster\/. Detailed proof of the propositions can also be found there.<\/jats:p>","DOI":"10.1093\/bioinformatics\/bth308","type":"journal-article","created":{"date-parts":[[2004,5,18]],"date-time":"2004-05-18T00:43:56Z","timestamp":1084841036000},"page":"2676-2684","source":"Crossref","is-referenced-by-count":2,"title":["An efficient algorithm for optimizing whole genome alignment with noise"],"prefix":"10.1093","volume":"20","author":[{"given":"Prudence W. H.","family":"Wong","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Hong Kong, Hong Kong"}]},{"given":"T. W.","family":"Lam","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Hong Kong, Hong Kong"}]},{"given":"N.","family":"Lu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Hong Kong, Hong Kong"}]},{"given":"H. F.","family":"Ting","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Hong Kong, Hong Kong"}]},{"given":"S. M.","family":"Yiu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Hong Kong, Hong Kong"}]}],"member":"286","published-online":{"date-parts":[[2004,5,14]]},"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/20\/16\/2676\/48906268\/bioinformatics_20_16_2676.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/20\/16\/2676\/48906268\/bioinformatics_20_16_2676.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T16:12:48Z","timestamp":1674663168000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/20\/16\/2676\/236700"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,5,14]]},"references-count":0,"journal-issue":{"issue":"16","published-print":{"date-parts":[[2004,11,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bth308","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2004,11,1]]},"published":{"date-parts":[[2004,5,14]]}}}