Discrete Optimization for TSP-like Genome Mapping Problems

ویرایش:  
نویسندگان: Mester D. etc.  
سری:  
 
ناشر:  
سال نشر:  
تعداد صفحات: [73] 
زبان: English 
فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) 
حجم فایل: 1 Mb 

قیمت کتاب (تومان) : 34,000

Издательство Nova Science Publishers, 2010, -73 pp. چند مشکل در تجزیه و تحلیل نقشه برداری ژنوم مدرن به حوزه بهینه سازی گسسته بر روی مجموعه ای از تمام سفارشات ممکن تعلق دارد. در اینجا ما فرمول‌بندی‌ها، مدل‌های ریاضی و الگوریتم‌هایی را برای مسئله نقشه‌برداری ژنتیکی/ژنومی توضیح می‌دهیم که می‌توانند در شرایط TSP مانند ارائه شوند. این موارد عبارتند از: ترتیب مکان های نشانگر (یا ژن ها) در نقشه برداری ژنتیکی چند جایگاهی (MGM)، نقشه برداری اجماع چند جایگاهی (MCGM)، و مشکل نقشه برداری فیزیکی (PMP). همه این مشکلات به دلیل نمرات نشانگرهای پر سر و صدا، مجموعه داده‌های بزرگ، محدودیت‌های خاص در کلاس‌های خاصی از سفارش‌ها و سایر عوارض، از نظر محاسباتی چالش برانگیز در نظر گرفته می‌شوند. وجود محدودیت‌های خاص در ترتیب برخی از عناصر در این مسائل اجازه نمی‌دهد تا به طور موثر الگوریتم‌های بهینه‌سازی گسسته معروف و قدرتمندی مانند Cutting-plane، الگوریتم ژنتیک با متقاطع EAX و Lin-Kernighan معروف را اعمال کنیم. در این مقاله نشان می‌دهیم که الگوریتم‌های استراتژی تکامل هدایت‌شده توسط ما این دسته از مسائل بهینه‌سازی محدود گسسته را با موفقیت حل می‌کنند. کارایی الگوریتم پیشنهادی بر روی مسائل استاندارد TSP و در سه مسئله ژنتیکی/ژنومی با حداکثر 2500 امتیاز نشان داده شده است. الگوریتم برای TSP کلاسیک به عنوان مبنایی برای حل مسائل ژنتیکی/ژنومی مانند TSP
نقشه ژنتیکی چند جایگاهی
نقشه ژنتیکی اجماع چند جایگاهی: فرمول بندی، مدل و الگوریتم ها
مسئله مشابه TSP در نقشه برداری فیزیکی ( PMP)
نتیجه گیری
انتخاب مقدار آستانه Q برای محاسبه PRC

Издательство Nova Science Publishers, 2010, -73 pp. Several problems in modern genome mapping analysis belong to the field of discrete optimization on a set of all possible orders. Here we describe formulations, mathematical models and algorithms for genetic/genomic mapping problem, that can be presented in TSP-like terms. These include: ordering of marker loci (or genes) in multilocus genetic mapping (MGM), multilocus consensus mapping (MCGM), and physical mapping problem (PMP). All these problems are considered as computationally challenging because of noisy marker scores, large-size data sets, specific constraints on certain classes of orders, and other complications. The presence of specific constrains on ordering of some elements in these problems does not allow applying effectively the well-known powerful discrete optimization algorithms like Cutting-plane, Genetic algorithm with EAX crossover and famous Lin-Kernighan. In the paper we demonstrate that developed by us Guided Evolution Strategy algorithms successfully solves this class of discrete constrained optimization problems. The efficiency of the proposed algorithm is demonstrated on standard TSP problems and on three genetic/genomic problems with up to 2,500 points. General Introduction
Guided Evolution Strategy Algorithm for Classic TSP as a Basis for Solving the Genetic/Genomic TSP-Like Problems
Multilocus Genetic Mapping
Multilocus Consensus Genetic Mapping: Formulation, Model and Algorithms
TSP-Like Problem in Physical Mapping (PMP)
Conclusions
Choosing Threshold Q Value for PRC Calculation