his.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Metaheuristic Multiple Sequence Alignment Optimisation
University of Skövde, School of Humanities and Informatics.
2004 (Swedish)Independent thesis Advanced level (degree of Master (One Year))Student thesis
Abstract [sv]

The ability to tackle NP-hard problems has been greatly extended by the introduction of Metaheuristics (see Blum & Roli (2003)) for a summary of most Metaheuristics, general problem-independent optimisation algorithms extending the hill-climbing local search approach to escape local minima. One of these algorithms is Iterated Local Search (ILS) (Lourenco et al., 2002; Stützle, 1999a, p. 25ff), a recent easy to implement but powerful algorithm with results comparable or superior to other state-of-the-art methods for many combinatorial optimisation problems, among them the Traveling Salesman (TSP) and Quadratic Assignment Problem (QAP). ILS iteratively samples local minima by modifying the current local minimum and restarting

a local search porcedure on this modified solution. This thesis will show how ILS can be implemented for MSA. After that, ILS will be evaluated and compared to other MSA algorithms by BAliBASE (Thomson et al., 1999), a set of manually refined alignments used in most recent publications of algorithms and in at least two MSA algorithm surveys. The runtime-behaviour will be evaluated using runtime-distributions.

The quality of alignments produced by ILS is at least as good as the best algorithms available and significantly superiour to previously published Metaheuristics for MSA, Tabu Search and Genetic Algorithm (SAGA). On the average, ILS performed best in five out of eight test cases, second for one test set and third for the remaining two. A drawback of all iterative methods for MSA is the long runtime needed to produce good alignments. ILS needs considerably less runtime than Tabu Search and SAGA, but can not compete with progressive or consistency based methods, e. g. ClustalW or T-COFFEE.

Place, publisher, year, edition, pages
Skövde: Institutionen för kommunikation och information , 2004. , 79 p.
Keyword [en]
Metaheuristic Multiple Sequence Alignment Optimisation
National Category
Computer Science
Identifiers
URN: urn:nbn:se:his:diva-899OAI: oai:DiVA.org:his-899DiVA: diva2:3318
Presentation
(English)
Uppsok
teknik
Supervisors
Available from: 2008-02-27 Created: 2008-02-27 Last updated: 2009-05-08

Open Access in DiVA

fulltext(2303 kB)146 downloads
File information
File name FULLTEXT01.psFile size 2303 kBChecksum SHA-1
24b8b81362b5784a2b9784ad38d8965b3b8ea917acf95ddbb23395241228c7f5f26a3699
Type fulltextMimetype application/postscript
fulltext(986 kB)622 downloads
File information
File name FULLTEXT02.pdfFile size 986 kBChecksum SHA-512
610c2d821ad21031fc84da205d5403249458065efa9210b2197ac479643e0bd096dd9db319f722bb4f74f9474ce7a525926c9049b6ed23b8e90ff8546a6f264b
Type fulltextMimetype application/pdf

By organisation
School of Humanities and Informatics
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 768 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 258 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf