05223nam 2200541 450 991083089430332120200914221619.01-119-13680-61-119-13679-2(CKB)4330000000008823(EBL)4648721(MiAaPQ)EBC4648721(CaSebORM)9781848218123(EXLCZ)99433000000000882320160903h20162016 uy 0engur|n|---|||||rdacontentrdamediardacarrierMetaheuristics for string problems in bio-informatics /Christian Blum, Paola FestaLondon, England ;Hoboken, New Jersey :ISTE :Wiley,2016.©20161 online resource (232 p.)Computer Engineering SeriesDescription based upon print version of record.1-84821-812-5 Includes bibliographical references and index.Cover ; Dedication; Title Page ; Copyright ; Contents; Preface; Acknowledgments; List of Acronyms; 1. Introduction; 1.1. Complete methods for combinatorial optimization; 1.1.1. Linear programming relaxation; 1.1.2. Cutting plane techniques; 1.1.3. General-purpose ILP solvers; 1.1.4. Dynamic programming; 1.2. Approximate methods: metaheuristics; 1.2.1. Ant colony optimization; 1.2.2. Evolutionary algorithms; 1.2.3. Greedy randomized adaptive search procedures; 1.2.4. Iterated local search; 1.2.5. Simulated annealing; 1.2.6. Other metaheuristics; 1.2.7. Hybrid approaches1.3. Outline of the book2. Minimum Common String Partition Problem; 2.1. The MCSP problem; 2.1.1. Technical description of the UMCSP problem; 2.1.2. Literature review; 2.1.3. Organization of this chapter; 2.2. An ILP model for the UMCSP problem; 2.3. Greedy approach; 2.4. Construct, merge, solve and adapt; 2.5. Experimental evaluation; 2.5.1. Benchmarks; 2.5.2. Tuning CMSA; 2.5.3. Results; 2.6. Future work; 3. Longest Common Subsequence Problems; 3.1. Introduction; 3.1.1. LCS problems; 3.1.2. ILP models for LCS and RFLCS problems; 3.1.3. Organization of this chapter3.2. Algorithms for the LCS problem 3.2.1. Beam search; 3.2.2. Upper bound; 3.2.3. Beam search framework; 3.2.4. Beam-ACO; 3.2.5. Experimental evaluation; 3.3. Algorithms for the RFLCS problem; 3.3.1. CMSA; 3.3.2. Experimental evaluation; 3.4. Future work; 4. The Most Strings With Few Bad Columns Problem; 4.1. The MSFBC problem; 4.1.1. Literature review; 4.2. An ILP model for the MSFBC problem; 4.3. Heuristic approaches; 4.3.1. Frequency-based greedy; 4.3.2. Truncated pilot method; 4.4. ILP-based large neighborhood search; 4.5. Experimental evaluation; 4.5.1. Benchmarks; 4.5.2. Tuning of LNS4.5.3. Results4.6. Future work; 5. Consensus String Problems; 5.1. Introduction; 5.1.1. Creating diagnostic probes for bacterial infections; 5.1.2. Primer design; 5.1.3. Discovering potential drug targets; 5.1.4. Motif search; 5.2. Organization of this chapter; 5.3. The closest string problem and the close to most string problem; 5.3.1. ILP models for the CSP and the CTMSP; 5.3.2. Literature review; 5.3.3. Exact approaches for the CSP; 5.3.4. Approximation algorithms for the CSP; 5.3.5. Heuristics and metaheuristics for the CSP5.4. The farthest string problem and the far from most string problem5.4.1. ILP models for the FSP and the FFMSP; 5.4.2. Literature review; 5.4.3. Heuristics and metaheuristics for the FFMSP; 5.5. An ILP-based heuristic; 5.6. Future work; 6. Alignment Problems; 6.1. Introduction; 6.1.1. Organization of this chapter; 6.2. The pairwise alignment problem; 6.2.1. Smith and Waterman's algorithm; 6.3. The multiple alignment problem; 6.3.1. Heuristics for the multiple alignment problem; 6.3.2. Metaheuristics for the multiple alignment problem; 6.4. Conclusion and future work; 7. Conclusions7.1. DNA sequencingThis book will present the latest research on metaheuristic algorithms for some of the most important string problems in bio-informatics. Optimization problems related to strings-such as protein or DNA sequences-are very common in bioinformatics. Examples include string selection problems such as the "far from most string" problem, and other string problems such as the longest common subsequence problem and its variants, alignment problems, and similarity search. These problems are often computationally very hard. Therefore, during the last 10-15 years the research community has focused especially on metaheuristic algorithms for solving this type of problems. This book aims at presenting some of the most interesting recent work in this line of research.--Source other than Library of Congress.Computer engineering series (London, England)BioinformaticsBioinformatics.572.80285Blum C(Christian),1648993Festa PaolaMiAaPQMiAaPQMiAaPQBOOK9910830894303321Metaheuristics for string problems in bio-informatics3997482UNINA