| |
|
|
|
|
|
|
|
|
1. |
Record Nr. |
UNINA9910830894303321 |
|
|
Autore |
Blum C (Christian) |
|
|
Titolo |
Metaheuristics for string problems in bio-informatics / / Christian Blum, Paola Festa |
|
|
|
|
|
|
|
Pubbl/distr/stampa |
|
|
London, England ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2016 |
|
©2016 |
|
|
|
|
|
|
|
|
|
ISBN |
|
1-119-13680-6 |
1-119-13679-2 |
|
|
|
|
|
|
|
|
Descrizione fisica |
|
1 online resource (232 p.) |
|
|
|
|
|
|
Collana |
|
Computer Engineering Series |
|
|
|
|
|
|
Disciplina |
|
|
|
|
|
|
Soggetti |
|
|
|
|
|
|
Lingua di pubblicazione |
|
|
|
|
|
|
Formato |
Materiale a stampa |
|
|
|
|
|
Livello bibliografico |
Monografia |
|
|
|
|
|
Note generali |
|
Description based upon print version of record. |
|
|
|
|
|
|
Nota di bibliografia |
|
Includes bibliographical references and index. |
|
|
|
|
|
|
Nota di contenuto |
|
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 approaches |
1.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 chapter |
3.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 LNS |
4.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 CSP |
5.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. Conclusions |
7.1. DNA sequencing |
|
|
|
|
|
|
Sommario/riassunto |
|
This 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.-- |
|
|
|
|
|
|
|
| |