<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head>
<title>UTas ePrints - MAUSA: Using Simulated Annealing for Guide Tree Construction in Multiple Sequence Alignment</title>
<script type="text/javascript" src="http://eprints.utas.edu.au/javascript/auto.js"><!-- padder --></script>
<style type="text/css" media="screen">@import url(http://eprints.utas.edu.au/style/auto.css);</style>
<style type="text/css" media="print">@import url(http://eprints.utas.edu.au/style/print.css);</style>
<link rel="icon" href="/images/eprints/favicon.ico" type="image/x-icon" />
<link rel="shortcut icon" href="/images/eprints/favicon.ico" type="image/x-icon" />
<link rel="Top" href="http://eprints.utas.edu.au/" />
<link rel="Search" href="http://eprints.utas.edu.au/cgi/search" />
<meta content="Uren, Philip" name="eprints.creators_name" />
<meta content="Cameron-Jones, Mike" name="eprints.creators_name" />
<meta content="Sale, Arthur" name="eprints.creators_name" />
<meta content="Philip.Uren@utas.edu.au" name="eprints.creators_id" />
<meta content="Michael.CameronJones@utas.edu.au" name="eprints.creators_id" />
<meta content="Arthur.Sale@utas.edu.au" name="eprints.creators_id" />
<meta content="conference_item" name="eprints.type" />
<meta content="2007-12-12 23:02:46" name="eprints.datestamp" />
<meta content="2008-01-08 15:30:00" name="eprints.lastmod" />
<meta content="show" name="eprints.metadata_visibility" />
<meta content="MAUSA: Using Simulated Annealing for Guide Tree Construction in Multiple Sequence Alignment" name="eprints.title" />
<meta content="pub" name="eprints.ispublished" />
<meta content="280213" name="eprints.subjects" />
<meta content="restricted" name="eprints.full_text_status" />
<meta content="paper" name="eprints.pres_type" />
<meta content="Multiple Sequence Alignment, Simulated Annealing, Guide Tree" name="eprints.keywords" />
<meta content="(The original publication is available at www.springerlink.com)" name="eprints.note" />
<meta content="Multiple sequence alignment is a crucial technique for many fields of computational biology and remains a difficult task. Combining several different alignment techniques often leads to the best results in practice. Within this paper we present MAUSA (Multiple Alignment Using Simulated Annealing) and show that the conceptually simple approach of simulated annealing, when combined with a recent development in solving the aligning alignments problem, produces results which are competitive and in some cases superior to established methods for sequence alignment. We show that the application of simulated annealing to effective guide tree selection improves the quality of the alignments produced. In addition, we apply a method for the automatic assessment of alignment quality and show that in scenarios where MAUSA is selected as producing the best alignment from a suite of approaches (approximately 10% of test cases), it produces an average 5% (p = 0.005, Wilcoxon sign-rank test) improvement in quality." name="eprints.abstract" />
<meta content="2007-12" name="eprints.date" />
<meta content="published" name="eprints.date_type" />
<meta content="10" name="eprints.pages" />
<meta content="Twentieth Australian Joint Conference on Artificial Intelligence" name="eprints.event_title" />
<meta content="Surfers Paradise, Gold Coast, Queensland, Australia" name="eprints.event_location" />
<meta content="2-6 December, 2007" name="eprints.event_dates" />
<meta content="conference" name="eprints.event_type" />
<meta content="TRUE" name="eprints.refereed" />
<meta content="http://dx.doi.org/10.1007/978-3-540-76928-6_61" name="eprints.official_url" />
<meta content="1. Notredame, C.: Recent progresses in multiple sequence alignment: a survey: Pharmacogenomics,
vol. 3, pp. 131–144 (2002)
2. Wang, L., Jiang, T.: On the complexity of multiple sequence alignment. J. Comput.
Biol. 1, 337–348 (1994)
3. Feng, D.F., Doolittle, R.F.: Progressive sequence alignment as a prerequisite to correct
phylogenetic trees: J. Mol. Evol. 25, 351–360 (1987)
4. Kirkpatrick, S., Gelatt, C.D., Vecci, M.P.: Optimization by simulated annealing: Science
220, 671–680 (1983)
5. Carrillo, H., Lipman, D.J.: The multiple sequence alignment problem in biology: SIAM
journal on applied mathematics 48, 1073–1082 (1988)
6. Lipman, D.J., Altschul, S.F., Kececioglu, J.: A tool for multiple sequence alignment: Proc.
Natl. Acad. Sci. 86, 4412–4415 (1989)
7. Kececioglu, J., Starrett, D.: In: RECOMB. Aligning alignments exactly: 8th ACM Conf.
on Computational Molecular Biology, pp. 85–96 (2004)
8. Notredame, C., Higgins, D.G., Heringa, J.: T-Coffee: a novel method for fast and accurate
multiple sequence alignment: Journal of Molecular Biology 302, 205–217 (2000)
9. Edgar, R.C.: MUSCLE: multiple sequence alignment with high accuracy and high
throughput: Nucleic Acids Research 32, 1792–1797 (2004)
10. Thompson, J.D., Higgins, D.G., Gibson, T.J.: CLUSTAL W: improving the sensitivity of
progressive multiple sequence alignment through sequence weighting, position- specific
gap penalties and weight matrix choice: Nucl. Acids Res. 22, 4673–4680 (1994)
11. Kim, J., Pramanik, S., Chung, M.J.: Multiple sequence alignment using simulated annealing:
Computer Applications in the Biosciences 10, 419–426 (1994)
12. Ishikawa, M., Toya, T., Hoshida, M., Nitta, K., Ogiwara, A., Kanehisa, M.: Multiple sequence
alignment by parallel simulated annealing: Comput. Appl. Biosci. 9, 267–273 (1993)
13. Hernandez-Guia, M., Mulet, R., Rodriguez-Perez, S.: A New Simulated Annealing Algorithm
for the Multiple Sequence Alignment Problem: The approach of Polymers in a Random
Media: Phys. Rev. E. 72, 031915 (2005)
14. Keith, J.M., Adams, P., Bryant, D., Kroese, D.P., Mitchelson, K.R., Cochran, D.A.E.,
Lala, G.H.: A simulated annealing algorithm for finding consensus sequences: Bioinformatics
18, 1494–1499 (2002)
15. Frith, M.C., Hansen, U., Spouge, J.L., Weng, Z.: Finding functional sequence elements by
multiple local alignment: Nucl. Acids Res. 32, 189–200 (2004)
16. Koller, G., Raidl, G.R.: An evolutionary algorithm for the maximum weight trace formulation
of the multiple sequence alignment problem: Parallel Problem Solving from Nature -
PPSN VIII, pp. 302–311 (2004)
17. Fleissner, R., Metzler, D., von Haeseler, A.: Simultaneous statistical multiple alignment
and phylogeny reconstruction: Systematic Biology 54, 548–561 (2005)
18. Thompson, J.D., Plewniak, F., Poch, O.: BAliBASE: a benchmark alignment database for
the evaluation of multiple alignment programs: Bioinformatics 15, 87–88 (1999)
19. Thompson, J.D., Koehl, P., Ripp, R., Poch, O.: BAliBASE 3.0: Latest developments of the
multiple sequence alignment benchmark: Proteins: Structure, Function, and Bioinformatics
61, 127–136 (2005)
20. Lassmann, T., Sonnhammer, E.L.L.: Automatic assessment of alignment quality: Nucl.
Acids Res. 33, 7120–7128 (2005)
21. Henikoff, S., Henikoff, J.G.: Amino acid substitution matrices from protein blocks: Proc.
Natl. Acad. Sci. 89, 10915–10919 (1992)
22. Marsh, T.L., Reich, C.I., Whitelock, R.B., Olsen, G.J.: Transcription factor IID in the Archaea:
Sequences in the Thermococcus celer genome would encode a product closely related
to the TATA-binding protein of eukaryotes: Proc. Natl. Acad. Sci. USA 91, 4180–
4184 (1994)
23. Reese, J.T., Pearson, W.R.: Empirical determination of effective gap penalties for sequence
comparison: Bioinformatics 18, 1500–1507 (2002)
24. Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions and reversals:
Sov. Phys. Dokl. 6, 707–710 (1966)" name="eprints.referencetext" />
<meta content="Uren, Philip and Cameron-Jones, Mike and Sale, Arthur (2007) MAUSA: Using Simulated Annealing for Guide Tree Construction in Multiple Sequence Alignment. In: Twentieth Australian Joint Conference on Artificial Intelligence, 2-6 December, 2007, Surfers Paradise, Gold Coast, Queensland, Australia." name="eprints.citation" />
<meta content="http://eprints.utas.edu.au/2640/1/MAUSA_AI07.pdf" name="eprints.document_url" />
<link rel="schema.DC" href="http://purl.org/DC/elements/1.0/" />
<meta content="MAUSA: Using Simulated Annealing for Guide Tree Construction in Multiple Sequence Alignment" name="DC.title" />
<meta content="Uren, Philip" name="DC.creator" />
<meta content="Cameron-Jones, Mike" name="DC.creator" />
<meta content="Sale, Arthur" name="DC.creator" />
<meta content="280213 Other Artificial Intelligence" name="DC.subject" />
<meta content="Multiple sequence alignment is a crucial technique for many fields of computational biology and remains a difficult task. Combining several different alignment techniques often leads to the best results in practice. Within this paper we present MAUSA (Multiple Alignment Using Simulated Annealing) and show that the conceptually simple approach of simulated annealing, when combined with a recent development in solving the aligning alignments problem, produces results which are competitive and in some cases superior to established methods for sequence alignment. We show that the application of simulated annealing to effective guide tree selection improves the quality of the alignments produced. In addition, we apply a method for the automatic assessment of alignment quality and show that in scenarios where MAUSA is selected as producing the best alignment from a suite of approaches (approximately 10% of test cases), it produces an average 5% (p = 0.005, Wilcoxon sign-rank test) improvement in quality." name="DC.description" />
<meta content="2007-12" name="DC.date" />
<meta content="Conference or Workshop Item" name="DC.type" />
<meta content="PeerReviewed" name="DC.type" />
<meta content="application/pdf" name="DC.format" />
<meta content="http://eprints.utas.edu.au/2640/1/MAUSA_AI07.pdf" name="DC.identifier" />
<meta content="http://dx.doi.org/10.1007/978-3-540-76928-6_61" name="DC.relation" />
<meta content="Uren, Philip and Cameron-Jones, Mike and Sale, Arthur (2007) MAUSA: Using Simulated Annealing for Guide Tree Construction in Multiple Sequence Alignment. In: Twentieth Australian Joint Conference on Artificial Intelligence, 2-6 December, 2007, Surfers Paradise, Gold Coast, Queensland, Australia." name="DC.identifier" />
<meta content="http://eprints.utas.edu.au/2640/" name="DC.relation" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/BibTeX/epprod-eprint-2640.bib" title="BibTeX" type="text/plain" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/ContextObject/epprod-eprint-2640.xml" title="OpenURL ContextObject" type="text/xml" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/ContextObject::Dissertation/epprod-eprint-2640.xml" title="OpenURL Dissertation" type="text/xml" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/ContextObject::Journal/epprod-eprint-2640.xml" title="OpenURL Journal" type="text/xml" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/DC/epprod-eprint-2640.txt" title="Dublin Core" type="text/plain" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/DIDL/epprod-eprint-2640.xml" title="DIDL" type="text/xml" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/EndNote/epprod-eprint-2640.enw" title="EndNote" type="text/plain" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/HTML/epprod-eprint-2640.html" title="HTML Citation" type="text/html; charset=utf-8" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/METS/epprod-eprint-2640.xml" title="METS" type="text/xml" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/MODS/epprod-eprint-2640.xml" title="MODS" type="text/xml" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/RIS/epprod-eprint-2640.ris" title="Reference Manager" type="text/plain" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/Refer/epprod-eprint-2640.refer" title="Refer" type="text/plain" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/Simple/epprod-eprint-2640text" title="Simple Metadata" type="text/plain" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/Text/epprod-eprint-2640.txt" title="ASCII Citation" type="text/plain; charset=utf-8" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/2640/XML/epprod-eprint-2640.xml" title="EP3 XML" type="text/xml" />
</head>
<body bgcolor="#ffffff" text="#000000" onLoad="loadRoutine(); MM_preloadImages('images/eprints/ePrints_banner_r5_c5_f2.gif','images/eprints/ePrints_banner_r5_c7_f2.gif','images/eprints/ePrints_banner_r5_c8_f2.gif','images/eprints/ePrints_banner_r5_c9_f2.gif','images/eprints/ePrints_banner_r5_c10_f2.gif','images/eprints/ePrints_banner_r5_c11_f2.gif','images/eprints/ePrints_banner_r6_c4_f2.gif')">
<div class="ep_noprint"><noscript><style type="text/css">@import url(http://eprints.utas.edu.au/style/nojs.css);</style></noscript></div>
<table width="795" border="0" cellspacing="0" cellpadding="0">
<tr>
<td><script language="JavaScript1.2">mmLoadMenus();</script>
<table border="0" cellpadding="0" cellspacing="0" width="795">
<!-- fwtable fwsrc="eprints_banner_final2.png" fwbase="ePrints_banner.gif" fwstyle="Dreamweaver" fwdocid = "1249563342" fwnested="0" -->
<tr>
<td><img src="/images/eprints/spacer.gif" width="32" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="104" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="44" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="105" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="41" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="16" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="68" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="68" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="68" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="82" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="69" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="98" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="1" border="0" alt="" /></td>
</tr>
<tr>
<td colspan="12"><img name="ePrints_banner_r1_c1" src="/images/eprints/ePrints_banner_r1_c1.gif" width="795" height="10" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="10" border="0" alt="" /></td>
</tr>
<tr>
<td rowspan="6"><img name="ePrints_banner_r2_c1" src="/images/eprints/ePrints_banner_r2_c1.gif" width="32" height="118" border="0" alt="" /></td>
<td rowspan="5"><a href="http://www.utas.edu.au/"><img name="ePrints_banner_r2_c2" src="/images/eprints/ePrints_banner_r2_c2.gif" width="104" height="103" border="0" alt="" /></a></td>
<td colspan="10"><img name="ePrints_banner_r2_c3" src="/images/eprints/ePrints_banner_r2_c3.gif" width="659" height="41" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="41" border="0" alt="" /></td>
</tr>
<tr>
<td colspan="3"><a href="http://eprints.utas.edu.au/"><img name="ePrints_banner_r3_c3" src="/images/eprints/ePrints_banner_r3_c3.gif" width="190" height="31" border="0" alt="" /></a></td>
<td rowspan="2" colspan="7"><img name="ePrints_banner_r3_c6" src="/images/eprints/ePrints_banner_r3_c6.gif" width="469" height="37" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="31" border="0" alt="" /></td>
</tr>
<tr>
<td colspan="3"><img name="ePrints_banner_r4_c3" src="/images/eprints/ePrints_banner_r4_c3.gif" width="190" height="6" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="6" border="0" alt="" /></td>
</tr>
<tr>
<td colspan="2"><img name="ePrints_banner_r5_c3" src="/images/eprints/ePrints_banner_r5_c3.gif" width="149" height="1" border="0" alt="" /></td>
<td rowspan="2" colspan="2"><a href="/information.html" onMouseOut="MM_swapImgRestore();MM_startTimeout()" onMouseOver="MM_showMenu(window.mm_menu_0821132634_0,0,25,null,'ePrints_banner_r5_c5');MM_swapImage('ePrints_banner_r5_c5','','/images/eprints/ePrints_banner_r5_c5_f2.gif',1);"><img name="ePrints_banner_r5_c5" src="/images/eprints/ePrints_banner_r5_c5.gif" width="57" height="25" border="0" alt="About" /></a></td>
<td rowspan="2"><a href="/view/" onMouseOut="MM_swapImgRestore();MM_startTimeout()" onMouseOver="MM_showMenu(window.mm_menu_0821133021_1,0,25,null,'ePrints_banner_r5_c7');MM_swapImage('ePrints_banner_r5_c7','','/images/eprints/ePrints_banner_r5_c7_f2.gif',1);"><img name="ePrints_banner_r5_c7" src="/images/eprints/ePrints_banner_r5_c7.gif" width="68" height="25" border="0" alt="Browse" /></a></td>
<td rowspan="2"><a href="/perl/search/simple" onMouseOut="MM_swapImgRestore();MM_startTimeout()" onMouseOver="MM_showMenu(window.mm_menu_0821133201_2,0,25,null,'ePrints_banner_r5_c8');MM_swapImage('ePrints_banner_r5_c8','','/images/eprints/ePrints_banner_r5_c8_f2.gif',1);"><img name="ePrints_banner_r5_c8" src="/images/eprints/ePrints_banner_r5_c8.gif" width="68" height="25" border="0" alt="Search" /></a></td>
<td rowspan="2"><a href="/perl/register" onMouseOut="MM_swapImgRestore();MM_startTimeout();" onMouseOver="MM_showMenu(window.mm_menu_1018171924_3,0,25,null,'ePrints_banner_r5_c9');MM_swapImage('ePrints_banner_r5_c9','','/images/eprints/ePrints_banner_r5_c9_f2.gif',1);"><img name="ePrints_banner_r5_c9" src="/images/eprints/ePrints_banner_r5_c9.gif" width="68" height="25" border="0" alt="register" /></a></td>
<td rowspan="2"><a href="/perl/users/home" onMouseOut="MM_swapImgRestore();MM_startTimeout()" onMouseOver="MM_showMenu(window.mm_menu_0821133422_4,0,25,null,'ePrints_banner_r5_c10');MM_swapImage('ePrints_banner_r5_c10','','/images/eprints/ePrints_banner_r5_c10_f2.gif',1);"><img name="ePrints_banner_r5_c10" src="/images/eprints/ePrints_banner_r5_c10.gif" width="82" height="25" border="0" alt="user area" /></a></td>
<td rowspan="2"><a href="/help/" onMouseOut="MM_swapImgRestore();MM_startTimeout()" onMouseOver="MM_showMenu(window.mm_menu_0821133514_5,0,25,null,'ePrints_banner_r5_c11');MM_swapImage('ePrints_banner_r5_c11','','/images/eprints/ePrints_banner_r5_c11_f2.gif',1);"><img name="ePrints_banner_r5_c11" src="/images/eprints/ePrints_banner_r5_c11.gif" width="69" height="25" border="0" alt="Help" /></a></td>
<td rowspan="3" colspan="4"><img name="ePrints_banner_r5_c12" src="/images/eprints/ePrints_banner_r5_c12.gif" width="98" height="40" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="1" border="0" alt="" /></td>
</tr>
<tr>
<td rowspan="2"><img name="ePrints_banner_r6_c3" src="/images/eprints/ePrints_banner_r6_c3.gif" width="44" height="39" border="0" alt="ePrints home" /></td>
<td><a href="/" onMouseOut="MM_swapImgRestore()" onMouseOver="MM_swapImage('ePrints_banner_r6_c4','','/images/eprints/ePrints_banner_r6_c4_f2.gif',1);"><img name="ePrints_banner_r6_c4" src="/images/eprints/ePrints_banner_r6_c4.gif" width="105" height="24" border="0" alt="ePrints home" /></a></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="24" border="0" alt="" /></td>
</tr>
<tr>
<td><img name="ePrints_banner_r7_c2" src="/images/eprints/ePrints_banner_r7_c2.gif" width="104" height="15" border="0" alt="" /></td>
<td colspan="8"><img name="ePrints_banner_r7_c4" src="/images/eprints/ePrints_banner_r7_c4.gif" width="517" height="15" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="15" border="0" alt="" /></td>
</tr>
</table></td>
</tr>
<tr><td><table width="100%" style="font-size: 90%; border: solid 1px #ccc; padding: 3px"><tr>
<td align="left"><a href="http://eprints.utas.edu.au/cgi/users/home">Login</a> | <a href="http://eprints.utas.edu.au/cgi/register">Create Account</a></td>
<td align="right" style="white-space: nowrap">
<form method="get" accept-charset="utf-8" action="http://eprints.utas.edu.au/cgi/search" style="display:inline">
<input class="ep_tm_searchbarbox" size="20" type="text" name="q" />
<input class="ep_tm_searchbarbutton" value="Search" type="submit" name="_action_search" />
<input type="hidden" name="_order" value="bytitle" />
<input type="hidden" name="basic_srchtype" value="ALL" />
<input type="hidden" name="_satisfyall" value="ALL" />
</form>
</td>
</tr></table></td></tr>
<tr>
<td class="toplinks"><!-- InstanceBeginEditable name="content" -->
<div align="center">
<table width="720" class="ep_tm_main"><tr><td align="left">
<h1 class="ep_tm_pagetitle">MAUSA: Using Simulated Annealing for Guide Tree Construction in Multiple Sequence Alignment</h1>
<p style="margin-bottom: 1em" class="not_ep_block"><span class="person_name">Uren, Philip</span> and <span class="person_name">Cameron-Jones, Mike</span> and <span class="person_name">Sale, Arthur</span> (2007) <xhtml:em>MAUSA: Using Simulated Annealing for Guide Tree Construction in Multiple Sequence Alignment.</xhtml:em> In: Twentieth Australian Joint Conference on Artificial Intelligence, 2-6 December, 2007, Surfers Paradise, Gold Coast, Queensland, Australia.</p><p style="margin-bottom: 1em" class="not_ep_block"></p><table style="margin-bottom: 1em" class="not_ep_block"><tr><td valign="top" style="text-align:center"><a href="http://eprints.utas.edu.au/2640/1/MAUSA_AI07.pdf"><img alt="[img]" src="http://eprints.utas.edu.au/style/images/fileicons/application_pdf.png" class="ep_doc_icon" border="0" /></a></td><td valign="top"><a href="http://eprints.utas.edu.au/2640/1/MAUSA_AI07.pdf"><span class="ep_document_citation">PDF</span></a> - Full text restricted - Requires a PDF viewer<br />180Kb</td><td><form method="get" accept-charset="utf-8" action="http://eprints.utas.edu.au/cgi/request_doc"><input accept-charset="utf-8" value="3460" name="docid" type="hidden" /><div class=""><input value="Request a copy" name="_action_null" class="ep_form_action_button" onclick="return EPJS_button_pushed( '_action_null' )" type="submit" /> </div></form></td></tr></table><p style="margin-bottom: 1em" class="not_ep_block">Official URL: <a href="http://dx.doi.org/10.1007/978-3-540-76928-6_61">http://dx.doi.org/10.1007/978-3-540-76928-6_61</a></p><div class="not_ep_block"><h2>Abstract</h2><p style="padding-bottom: 16px; text-align: left; margin: 1em auto 0em auto">Multiple sequence alignment is a crucial technique for many fields of computational biology and remains a difficult task. Combining several different alignment techniques often leads to the best results in practice. Within this paper we present MAUSA (Multiple Alignment Using Simulated Annealing) and show that the conceptually simple approach of simulated annealing, when combined with a recent development in solving the aligning alignments problem, produces results which are competitive and in some cases superior to established methods for sequence alignment. We show that the application of simulated annealing to effective guide tree selection improves the quality of the alignments produced. In addition, we apply a method for the automatic assessment of alignment quality and show that in scenarios where MAUSA is selected as producing the best alignment from a suite of approaches (approximately 10% of test cases), it produces an average 5% (p = 0.005, Wilcoxon sign-rank test) improvement in quality.</p></div><table style="margin-bottom: 1em" cellpadding="3" class="not_ep_block" border="0"><tr><th valign="top" class="ep_row">Item Type:</th><td valign="top" class="ep_row">Conference or Workshop Item (Paper)</td></tr><tr><th valign="top" class="ep_row">Additional Information:</th><td valign="top" class="ep_row">(The original publication is available at www.springerlink.com)</td></tr><tr><th valign="top" class="ep_row">Keywords:</th><td valign="top" class="ep_row">Multiple Sequence Alignment, Simulated Annealing, Guide Tree</td></tr><tr><th valign="top" class="ep_row">Subjects:</th><td valign="top" class="ep_row"><a href="http://eprints.utas.edu.au/view/subjects/280213.html">280000 Information, Computing and Communication Sciences > 280200 Artificial Intelligence and Signal and Image Processing > 280213 Other Artificial Intelligence</a></td></tr><tr><th valign="top" class="ep_row">ID Code:</th><td valign="top" class="ep_row">2640</td></tr><tr><th valign="top" class="ep_row">Deposited By:</th><td valign="top" class="ep_row"><span class="ep_name_citation"><span class="person_name">Mr. Philip Uren</span></span></td></tr><tr><th valign="top" class="ep_row">Deposited On:</th><td valign="top" class="ep_row">13 Dec 2007 10:02</td></tr><tr><th valign="top" class="ep_row">Last Modified:</th><td valign="top" class="ep_row">09 Jan 2008 02:30</td></tr><tr><th valign="top" class="ep_row">ePrint Statistics:</th><td valign="top" class="ep_row"><a target="ePrintStats" href="/es/index.php?action=show_detail_eprint;id=2640;">View statistics for this ePrint</a></td></tr></table><p align="right">Repository Staff Only: <a href="http://eprints.utas.edu.au/cgi/users/home?screen=EPrint::View&eprintid=2640">item control page</a></p>
</td></tr></table>
</div>
<!-- InstanceEndEditable --></td>
</tr>
<tr>
<td><!-- #BeginLibraryItem "/Library/footer_eprints.lbi" -->
<table width="795" border="0" align="left" cellpadding="0" class="footer">
<tr valign="top">
<td colspan="2"><div align="center"><a href="http://www.utas.edu.au">UTAS home</a> | <a href="http://www.utas.edu.au/library/">Library home</a> | <a href="/">ePrints home</a> | <a href="/contact.html">contact</a> | <a href="/information.html">about</a> | <a href="/view/">browse</a> | <a href="/perl/search/simple">search</a> | <a href="/perl/register">register</a> | <a href="/perl/users/home">user area</a> | <a href="/help/">help</a></div><br /></td>
</tr>
<tr><td colspan="2"><p><img src="/images/eprints/footerline.gif" width="100%" height="4" /></p></td></tr>
<tr valign="top">
<td width="68%" class="footer">Authorised by the University Librarian<br />
© University of Tasmania ABN 30 764 374 782<br />
<a href="http://www.utas.edu.au/cricos/">CRICOS Provider Code 00586B</a> | <a href="http://www.utas.edu.au/copyright/copyright_disclaimers.html">Copyright & Disclaimers</a> | <a href="http://www.utas.edu.au/accessibility/index.html">Accessibility</a> | <a href="http://eprints.utas.edu.au/feedback/">Site Feedback</a> </td>
<td width="32%"><div align="right">
<p align="right" class="NoPrint"><a href="http://www.utas.edu.au/"><img src="http://www.utas.edu.au/shared/logos/unioftasstrip.gif" alt="University of Tasmania Home Page" width="260" height="16" border="0" align="right" /></a></p>
<p align="right" class="NoPrint"><a href="http://www.utas.edu.au/"><br />
</a></p>
</div></td>
</tr>
<tr valign="top">
<td><p> </p></td>
<td><div align="right"><span class="NoPrint"><a href="http://www.eprints.org/software/"><img src="/images/eprintslogo.gif" alt="ePrints logo" width="77" height="29" border="0" align="bottom" /></a></span></div></td>
</tr>
</table>
<!-- #EndLibraryItem -->
<div align="center"></div></td>
</tr>
</table>
</body>
</html>
