{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T13:40:10Z","timestamp":1737121210450,"version":"3.33.0"},"reference-count":30,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02a","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2007,4]]},"abstract":"<jats:p>A multi-locus likelihood of a genetic map is computed based on a mathematical model of chromatid exchange in meiosis that accounts for any type of bivalent configuration in a genetic interval in any specified order of genetic markers. The computational problem is to calculate the likelihood (L) and maximize L by choosing an ordering of genetic markers on the map and the recombination distances between markers. This maximum likelihood estimate (MLE) could be found either with a straightforward algorithm or with the proposed recursive linking algorithm that implements the likelihood computation process involving an iterative procedure is called Expectation Maximization (EM). The time complexity of the straightforward algorithm is exponential without bound in the number of genetic markers, and implementation of the model with a straightforward algorithm for more than seven genetic markers is not feasible, thus motivating the critical importance of the proposed recursive linking algorithm. The recursive linking algorithm decomposes the pool of genetic markers into segments and renders the model implementable for hundreds of genetic markers. The recursive algorithm is shown to reduce the order of time complexity from exponential to linear in the number of markers. The improvement in time complexity is shown theoretically by a worst-case analysis of the algorithm and supported by run time results using data on linkage group-II of the fungal genome Neurospora crassa.<\/jats:p>","DOI":"10.1142\/s0219720007002758","type":"journal-article","created":{"date-parts":[[2007,6,22]],"date-time":"2007-06-22T02:42:56Z","timestamp":1182480176000},"page":"201-250","source":"Crossref","is-referenced-by-count":1,"title":["DESIGN AND ANALYSIS OF AN EFFICIENT RECURSIVE LINKING ALGORITHM FOR CONSTRUCTING LIKELIHOOD BASED GENETIC MAPS FOR A LARGE NUMBER OF MARKERS"],"prefix":"10.1142","volume":"05","author":[{"given":"S.","family":"TEWARI","sequence":"first","affiliation":[{"name":"Department of Statistics, University of Georgia, Athens, GA 30602-1952, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. M.","family":"BHANDARKAR","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Georgia, Athens, GA 30602-7404, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"ARNOLD","sequence":"additional","affiliation":[{"name":"Department of Genetics, University of Georgia, Athens, GA 30602-7223, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1038\/nature04226"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2660(08)60127-3"},{"key":"rf3","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1093\/genetics\/132.2.591","volume":"132","author":"Cuticchia A. J.","journal-title":"Genetics"},{"key":"rf4","first-page":"1458","volume":"264","author":"Daphne P.","journal-title":"Science"},{"volume-title":"NEUROSPORA Contributions of a Model Organism","year":"2000","author":"Davis R. H.","key":"rf5"},{"key":"rf6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","volume":"39","author":"Dempster A.","journal-title":"J. Royal Stat. Soc. Series B"},{"key":"rf7","first-page":"195","volume":"12","author":"Doerge R. W.","journal-title":"Stat. Sci."},{"key":"rf8","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1093\/genetics\/133.3.681","volume":"133","author":"Foss E.","journal-title":"Genetics"},{"key":"rf9","first-page":"229","volume":"8","author":"Haldane J. B. S.","journal-title":"J. Genetics"},{"volume-title":"Java Software Solutions","year":"2004","author":"John L.","key":"rf10"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.84.8.2363"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1126\/science.8091226"},{"key":"rf14","first-page":"299","volume":"7","author":"Lange K.","journal-title":"The Annals of Applied Probability"},{"volume-title":"The Measurement of Linkage in Heredity","year":"1951","author":"Mather K.","key":"rf15"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1991.10475130"},{"key":"rf17","doi-asserted-by":"crossref","first-page":"2269","DOI":"10.1093\/genetics\/165.4.2269","volume":"165","author":"Mester D.","journal-title":"Genetics"},{"volume-title":"Univariate Discrete Distributions","year":"1993","author":"Norman L. J.","key":"rf19"},{"volume-title":"The Neurospora Compendium","year":"2001","author":"Perkins D.","key":"rf20"},{"key":"rf21","first-page":"208","volume":"23","author":"Raju N. B.","journal-title":"J. Eur. Biol. Cell."},{"volume-title":"Linear Statistical Inference and Its Application","year":"2002","author":"Rao C. R.","key":"rf22"},{"key":"rf23","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1007\/BF00211049","volume":"86","author":"Schwager S. J.","journal-title":"Theoretical and Applied Genetics\/Theoretische und angewandte Genetik"},{"volume-title":"Matrix Algebra Useful for Statistics","year":"1982","author":"Searle S. R.","key":"rf24"},{"volume-title":"Introduction to Algorithms","year":"2001","author":"Thomas H. C.","key":"rf26"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1016\/0888-7543(87)90050-4"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1126\/science.281.5380.1194"},{"key":"rf29","doi-asserted-by":"crossref","first-page":"1057","DOI":"10.1093\/genetics\/139.2.1057","volume":"139","author":"Zhao H.","journal-title":"Genetics"},{"key":"rf30","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.1093\/genetics\/139.2.1045","volume":"139","author":"Zhao H.","journal-title":"Genetics"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1080\/03610929808832177"},{"key":"rf32","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1093\/genetics\/150.1.459","volume":"150","author":"Zhao H.","journal-title":"Genetics"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720007002758","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T13:01:18Z","timestamp":1737118878000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720007002758"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4]]},"references-count":30,"journal-issue":{"issue":"02a","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2007,4]]}},"alternative-id":["10.1142\/S0219720007002758"],"URL":"https:\/\/doi.org\/10.1142\/s0219720007002758","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"type":"print","value":"0219-7200"},{"type":"electronic","value":"1757-6334"}],"subject":[],"published":{"date-parts":[[2007,4]]}}}