Variational Methods in Combinatorial Optimization and Phylogeny Reconstruction

Abstract

Algorithms based on the variational approach, as used in statistical physics, are developed. For constraint satisfaction problems a novel cost function, based on information-theoretic arguments, is introduced, and an algorithm similar to the mean-field annealing algorithm is proposed. It outperforms the conventional mean-field algorithm, and its performance is comparable to good problem-dedicated heuristics for KSAT and graph coloring. For nonlinear assignment problems, improvements to mean-field annealing algorithms based on Potts spins are suggested, and confirmed for TSP. Also a more proper variational approach to assignment problems is proposed and analysed. A novel variational approximation to maximum likelihood is introduced and applied to phylogeny reconstruction. In tests on artificial and real DNA-sequences, the performance is seen to be comparable to that of standard maximum likelihood for reasonably similar sequences.

Abstract (Swedish)

Popular Abstract in Swedish

Metoder utvecklade inom den statistiska fysiken har visat sig vara användbara även i andra forskningfält såsom datalogi, statistik, ekonomi och molekylärbiologi. I den här avhandlingen undersöks hur en variationell metod, utvecklad för statistisk fysik, kan användas när man löser kombinatoriska optimeringsproblem och när man försöker rekonstruera evolutionsträd.



I den statistiska fysiken utgår man från delarna av ett system för att försöka beskriva beteenden för hela systemet. T ex kan man använda sig av atomers egenskaper för att beskriva globala egenskaper hos gaser eller fasta material. Den variationella metod som används här går ut på att göra en förenklad approximation av partiklars magnetiska egenskaper beskrivna av deras spin. Approximationen optimeras sedan för att egenskaperna hos hela systemet skall beskrivas så bra som möjligt.



Första problemtypen som diskuteras är kombinatorisk optimering. Ett problem består av ett antal diskreta variabler, dvs variabler som kan vara i ett uppräkneligt antal tillstånd. En kostnad är kopplad till varje kombination av tillstånd som variablerna kan anta, och det gäller att minimera denna kostnad. Problemet är att antalet möjliga kombinationer växer exponentiellt med antalet variabler. Om variablerna t ex kan vara i två möjliga tillstånd kommer antalet möjliga variabelkombinationer fördubblas när en extra variabel införs och inte ens de snabbaste datorer kommer att kunna gå igenom alla möjliga tillstånd när antalet variabler växer. För att man skall vara säker på att tillståndet med minsta möjliga kostnad har hittats måste man dock ofta göra detta.



För att få en känsla för problemen kan en liknelse vara på sin plats. Tänk dig att du har en hög med pusselbitar. Bitarna kan komma från olika pussel och uppgiften är att avgöra huruvida det finns ett komplett pussel bland bitarna. Om du får ihop ett pussel har du bevisat att det finns genom att du visar upp pusslet, men om du misslyckas vet du inte om det beror på att det inte finns något pussel eller om du bara misslyckats att hitta det. För att bevisa att det inte finns något pussel måste man prova alla möjliga kombinationer av att sätta pusselbitarna på olika ställen i pusslet, vilket snabbt blir en omöjlighet när man har lite fler bitar.



Inom fysiken beskrivs ofta spin i form av diskreta variabler och man kan överföra optimeringsproblemet till ett system av spinvariabler och kostnaden kan beskrivas som energin hos systemet. Därmed kan man utnyttja metoder inom fysiken för att hitta energiminima hos spinsystem för att lösa kombinatoriska optimeringsproblem.



Den metod som används här är att utnyttja en medelfälts-approximation för spinvariablerna. Detta leder till att man kan minimera energin för ett spin i taget och man kan på så sätt hitta ett tillstånd med låg energi. Detta garanterar inte att man hittar den lägsta möjliga energin, men med hjälp av att man inför en temperaturparameter kan man sakta kyla systemet och samtidigt uppdatera spin variablerna, vilket leder till en ökad chans att hitta ett tillstånd med låg energi.



Ett annat problem där en medelfälts-approximation är användbar är när man försöker rekonstruera ett evolutionärt träd genom att titta på DNA-sekvenser från olika arter. Man antar att alla nu levande arter härstammar från en och samma "urfader". Man antar också att under evolutionens gång så delas grupper av en art upp (t ex geografiskt) så att de olika grupperna fortsättningsvis utvecklas oberoende av varandra. Delningarna upprepas genom historien tills man kommer fram till de olika arter som existerar nu. Om man tittar på en speciell del av DNA-sekvensen från olika arter kan man se att sekvenserna liknar varandra, men att det finns skillnader. Dessa skillnader antas bero på mutationer, och problemställningen är att genom skillnaderna i sekvenser försöka återskapa när uppdelningarna i olika arter har skett. Man kan använda sig av en matematisk modell för hur sekvenser muterar och kan då optimera dessa modeller för att få fram det evolutionsträd som är mest troligt enligt modellen. Problemet med detta förfarande är att då man uppdaterar (optimerar) parametrarna för modellen så måste man göra detta med hjälp av en iterativ uppdaterning. I denna avhandling föreslås istället en approximation, där man inför variabler (som kan ses som spin) för de "historiska" arter som beskriver sekvenserna vid de olika delningspunkterna i evolutionsträdet. Detta leder till explicita uppdateringsekvationer för modellparametrarna. Man måste nu även uppdatera variablerna för approximationen, men detta kan också göras med explicita uppdateringsekvationer.

• author: Jönsson, Henrik
• supervisor: [unknown] [unknown]
• opponent: Monasson, Remi
• organization: Computational Biology and Biological Physics - Has been reorganised
• publishing date: 2001
• type: Thesis
• publication status: published
• subject: Biophysics
• keywords: statistical physics, gravitation, relativity, annealing, variational, mean-field, phylogeny, constraint satisfaction, combinatorial optimization, maximum likelihood, Physics, Fysik, Mathematical and general theoretical physics, quantum mechanics, classical mechanics, klassisk mekanik, kvantmekanik, relativitet, statistisk fysik, termodynamik, Fysicumarkivet A:2001:Jönsson, Matematisk och allmän teoretisk fysik, thermodynamics
• pages: 128 pages
• defense location: Lecture hall F, Department of Theoretical Physics
• defense date: 2001-12-14 10:15:00
• ISBN: 91-7874-161-1
• language: English
• LU publication?: yes
• id: 54bbc330-8d59-414f-9a87-110949eb51af (old id 42162)
• date added to LUP: 2016-04-04 10:40:12
• date last changed: 2018-11-21 21:00:06