his.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Metaheuristic Multiple Sequence Alignment Optimisation
Högskolan i Skövde, Institutionen för kommunikation och information.
2004 (Svenska)Självständigt arbete på avancerad nivå (magisterexamen)Studentuppsats
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.

Ort, förlag, år, upplaga, sidor
Skövde: Institutionen för kommunikation och information , 2004. , s. 79
Nyckelord [en]
Metaheuristic Multiple Sequence Alignment Optimisation
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:his:diva-899OAI: oai:DiVA.org:his-899DiVA, id: diva2:3318
Presentation
(Engelska)
Uppsök
teknik
Handledare
Tillgänglig från: 2008-02-27 Skapad: 2008-02-27 Senast uppdaterad: 2018-01-12

Open Access i DiVA

fulltext(2303 kB)356 nedladdningar
Filinformation
Filnamn FULLTEXT01.psFilstorlek 2303 kBChecksumma SHA-1
24b8b81362b5784a2b9784ad38d8965b3b8ea917acf95ddbb23395241228c7f5f26a3699
Typ fulltextMimetyp application/postscript
fulltext(986 kB)793 nedladdningar
Filinformation
Filnamn FULLTEXT02.pdfFilstorlek 986 kBChecksumma SHA-512
610c2d821ad21031fc84da205d5403249458065efa9210b2197ac479643e0bd096dd9db319f722bb4f74f9474ce7a525926c9049b6ed23b8e90ff8546a6f264b
Typ fulltextMimetyp application/pdf

Av organisationen
Institutionen för kommunikation och information
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 1149 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 489 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf