Computational molecular biology: A survey of problems and tools

Abstract

We  are interested  in  computational problems motivated  by  molecular biology.  The problems  are  interesting and  practical  solutions are  much  needed.  Most  of  the  problems  one  runs into, almost  without  exceptions,  are  hard. Sometimes,  the  idealized problems,  assuming no experimental error,  are not  very  difficult-consider  the problem  of  sequencing using  k-tuple  probes.  This has  a  polynomial  lime  solution  but the  presence  of  experimental  errors makes the  problem  difficult. Thus,  in  most  cases  the task  then  is  to devise practical,  efficient approximate  algorithms.