Article View: bionet.software
Article #2405Re: sequence partitioning
From: Mikhail Fursov
Date: Thu, 04 Feb 2010 17:54
Date: Thu, 04 Feb 2010 17:54
74 lines
6483 bytes
6483 bytes
Hi Michal, Have you read about suffix arrays or suffix trees? http://en.wikipedia.org/wiki/Suffix_array The 'suffix' theory could help you in your task probably. On Feb 4, 12:38�am, Michal Walicki <Michal.Wali...@ii.uib.no> wrote: > Gentle people, > � I started to work with sequences a couple of months ago and > encountered a problem which may be different from those faced by > biological sequence analysis but, hopefully, you can give me an > answer or, at least, point me in the right direction. > > The problem: > partition a given sequence S into a minimal number of patterns. > > (We assume some finite alphabet and, of course, S is finite. The > problem gets a bit different flavour when S may not have a partition, > so let us assume that a partitioning of S is possible.) > > A pattern P is any sequence with all symbols distinct and length at least 2. > P occurs in a sequence S if P is a subsequence of S (not necessarily > a substring). > A subsequence of S is an > - do(P), disjoint occurence of P, if it consists of (at least 2) > disjoint occurrences of pattern P > and it is an > - mdo(P), maximal do(P), if it is do(P) and there are no occurrences > of P in the rest of S, i.e., in > S \ mdo(P) = the subsequence of S obtained by removing the subsequence mdo(P). > > A partition (exact cover) of a sequence S is given by > � �a) a set of mutually distinct (not necessarily disjoint) patterns > P1...Pn, with > � �b) mutually disjoint, nonempty subsequences do(P1)...do(Pn) of S which, > � �c) together, constitute the whole S. > It is minimal if there is no partition with a smaller set a) (with > fewer patterns). > It is MDO if all do(Pi) in point b) are, actually, mdo(Pi). > > Question 1. > The problem seems - obviously - NP-hard but does anybody know of a > proof of that? > > Question 2. > Suppose that > � � i) there is a minimal partition with N patterns, and > � �ii) there is some MDO partition (obviously, with at least N patterns). > Is there, then, an MDO partition with N patterns? > > Conjecture 2 (the answer Yes to question 2) is quite intriguing > since, on the one hand, it seems plausible - a minimal partition > should contain mdo's of involved patterns but, on the other hand, > there seems to be no reason why it should happen to be the case. (If > we drop the assumption ii), it is, in fact, wrong, i.e., there are > sequences which can be partitioned with N patterns, but which have no > MDO partition.) We have run tens of tests (on random sequences (with > exact partitions) up to 20-30 symbols) and never met a counterexample > to Conjecture 2. > > Any hints are appreciated > > � � � � Michal > -- > > -------------------- > Assoc. Prof. Michal Walicki > Institute of Informatics > University of Bergen > 5020 Bergen, Norwayhttp://www.ii.uib.no/~michal > (on leave at IST, Lisbon, until 8.2010)
Technical Details
Message-ID:
<mailman.33.1265307382.25217.bio-soft@net.bio.net>Path:
arc1-ca.pugleaf.net!g2news1.google.com!news1.google.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!news.giganews.com.POSTED!not-for-mailReferences:
<mailman.24.1265222260.25217.bio-soft@net.bio.net>Show Full Headers
Complete Article Headers
X-Google-Language: ENGLISH,ASCII Path: arc1-ca.pugleaf.net!g2news1.google.com!news1.google.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!news.giganews.com.POSTED!not-for-mail NNTP-Posting-Date: Thu, 04 Feb 2010 12:16:47 -0600 X-Envelope-From: news@google.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:received :x-authentication-warning:to:path:from:newsgroups:subject:date :organization:lines:message-id:references:nntp-posting-host :mime-version:content-type:content-transfer-encoding:x-trace :x-complaints-to:nntp-posting-date:complaints-to:injection-info :user-agent:x-http-via:x-http-useragent; bh=Ka+I9tbhyQywN/3AkL089oD8wltyujTSPPmv7ZJ3Q1k=; b=uxcZ0vqQGghIkkwKPF+8Pd0Nh6mwEaqYCNdOO1QC4QPAPoOa3zHMuFtKp4BF3FJwoY lYNdLHaVStzRVBr+aAwMu6rCZNW5dAc2qldJQHqu/xz1tZMBpF38o+v7DuKwndtU8hQX Swxp9EtfNqMo0zEec0UoziD8P7hFc8KUZGno4= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=x-authentication-warning:to:path:from:newsgroups:subject:date :organization:lines:message-id:references:nntp-posting-host :mime-version:content-type:content-transfer-encoding:x-trace :x-complaints-to:nntp-posting-date:complaints-to:injection-info :user-agent:x-http-via:x-http-useragent; b=Q2/XbxebwAtgvtH4gCDsQTjhT1mkzLeRQli8AK88BTw24rxpToRJyqZuGFLa0pBmp4 37KJL5fYW4oUW8I+u6wokigBwOyNDIpTXOjjoDfcCLBi5lqmDmEv86eOv/q2V/fBD9r+ l2u0n5VL+IVTP+U4KlQsaJIxJQZr7vL1Jccl4= X-Authentication-Warning: ywd9.prod.google.com: news set sender to news@google.com using -f To: bionet-software@moderators.isc.org From: Mikhail Fursov <mike.fursov@gmail.com> Date: Thu, 4 Feb 2010 09:54:01 -0800 (PST) Organization: http://groups.google.com References: <mailman.24.1265222260.25217.bio-soft@net.bio.net> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Complaints-To: groups-abuse@google.com Injection-Info: l19g2000yqb.googlegroups.com; posting-host=212.17.10.114; posting-account=GUh41QoAAAC2bcZAU6oyL7TynOgTtusR User-Agent: G2/1.0 X-HTTP-Via: 1.1 rio2.unipro.ru:8080 (squid/2.7.STABLE5) X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-GB; rv:1.9.1.7) Gecko/20091221 Firefox/3.5.7 (.NET CLR 3.5.30729), gzip(gfe), gzip(gfe) Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by net.bio.net id o14Hs4d04734 X-Mailman-Approved-At: Thu, 04 Feb 2010 13:16:20 -0500 X-BeenThere: bio-soft@net.bio.net X-Mailman-Version: 2.1.4 Precedence: list subject: Re: sequence partitioning Newsgroups: bionet.software Message-ID: <mailman.33.1265307382.25217.bio-soft@net.bio.net> Approved: BIOSCI Approval Key <biosci-approval-key@net.bio.net> X-Auth: PGPMoose V1.1 PGP bionet.software iQCVAwUBS2sO96CIqsWvyF5FAQGRqwP/eEGCTDAvjz9DlW+EGTpNRuJLdj2akssm ISCnIX/+B/0AeDOTsG7OMNQWg0/XLFC/VKhsgiF9sZ3wj8Y5OHpGwZhkAAo3OHiU Ze+4t/Sw22VmHeBzZG2ns0pi9OiMWklga3AXWZtFQ59AXKlbC5seqY7JCD9Yvveh 63/ONz/OjIw= =4IRB Lines: 76 X-Usenet-Provider: http://www.giganews.com X-Trace: sv3-5dcu4MJgdwkzJxn8EQ63kJC/sVH0s/rT4b/0aaPNSSOumAS+dPKMLCStWj/NKwsHE+65B+5raW1jcXn!BxnBpCYR4o7ZXDrlAaAL4z3yB5s4DmeFGRAuKFB3wlUWOsR918JPCSkfv+YbHC9jcVd6gpxFqRN4!5BU= X-Complaints-To: abuse@giganews.com X-DMCA-Notifications: http://www.giganews.com/info/dmca.html X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40