23151d9021cf

REVP
[view raw] [browse files]
author Steve Losh <steve@stevelosh.com>
date Thu, 08 Nov 2018 22:06:36 -0500
parents b3598dc7ef5c
children 7fd1feb477de
branches/tags (none)
files rosalind.asd src/problems/grph.lisp src/problems/orf.lisp src/problems/revp.lisp

Changes

--- a/rosalind.asd	Thu Nov 08 21:17:47 2018 -0500
+++ b/rosalind.asd	Thu Nov 08 22:06:36 2018 -0500
@@ -49,6 +49,7 @@
                                            (:file "prot")
                                            (:file "prtm")
                                            (:file "revc")
+                                           (:file "revp")
                                            (:file "rna")
                                            (:file "splc")
                                            (:file "subs")
--- a/src/problems/grph.lisp	Thu Nov 08 21:17:47 2018 -0500
+++ b/src/problems/grph.lisp	Thu Nov 08 22:06:36 2018 -0500
@@ -1,6 +1,7 @@
 (in-package :rosalind)
 
-(defparameter *input-grph* ">Rosalind_0498
+(defparameter *input-grph*
+  ">Rosalind_0498
 AAATAAA
 >Rosalind_2391
 AAATTTT
@@ -11,8 +12,9 @@
 >Rosalind_5013
 GGGTGGG")
 
-(defparameter *output-grph* "Rosalind_0498 Rosalind_2391
-Rosalind_0498 Rosalind_0442
+(defparameter *output-grph*
+  "Rosalind_0498 Rosalind_0442
+Rosalind_0498 Rosalind_2391
 Rosalind_2391 Rosalind_2323
 ")
 
@@ -48,9 +50,10 @@
              data)
     ;; (ql:quickload :cl-digraph.dot)
     ;; (digraph.dot:draw graph)
-    (with-output-to-string (s)
-      (iterate (for (l . r) :in (digraph:edges graph))
-               (format s "~A ~A~%" l r)))))
+    (-<> (iterate (for (l . r) :in (digraph:edges graph))
+                  (collect (format nil "~A ~A~%" l r)))
+      (sort <> #'string<)
+      (str:join nil <>))))
 
 
 
--- a/src/problems/orf.lisp	Thu Nov 08 21:17:47 2018 -0500
+++ b/src/problems/orf.lisp	Thu Nov 08 22:06:36 2018 -0500
@@ -25,11 +25,10 @@
   (let* ((dna (cdr (first (read-fasta-into-alist data))))
          (rna1 (transcribe dna))
          (rna2 (transcribe (reverse-complement dna))))
-    (with-output-to-string (s)
-      (-<> (append (translate-all rna1)
-                   (translate-all rna2))
-        (remove-duplicates <> :test #'string=)
-        (sort <> #'< :key #'length)
-        (format s "~{~A~^~%~}" <>)))))
+    (-<> (append (translate-all rna1)
+                 (translate-all rna2))
+      (remove-duplicates <> :test #'string=)
+      (sort <> #'< :key #'length)
+      (format nil "~{~A~^~%~}" <>))))
 
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/revp.lisp	Thu Nov 08 22:06:36 2018 -0500
@@ -0,0 +1,51 @@
+(in-package :rosalind)
+
+;; The problem explanation provided a clever trick: you can cut the comparison
+;; size in half by comparing the first half of the string to the reverse
+;; complement of the second half, instead of comparing the entire thing.
+;;
+;; AAC GTT
+;;     CAA complement
+;;     AAC reverse
+;; AAC=AAC palindrome!
+
+(defparameter *input-revp*
+  ">Rosalind_24
+TCAATGCATGCGGGTCTATATGCAT")
+
+(defparameter *output-revp*
+  "4 6
+5 4
+6 6
+7 4
+17 4
+18 4
+20 6
+21 4
+")
+
+
+(defun reverse-palindrome-p (dna start length)
+  (let ((mid (+ start (truncate length 2)))
+        (end (+ start length)))
+    (unless (> end (length dna))
+      (string= dna
+               (reverse-complement (subseq dna mid end))
+               :start1 start
+               :end1 mid))))
+
+(defun reverse-palindrome-length (dna start)
+  (iterate (for i :from 12 :downto 4 :by 2)
+           (finding i :such-that (reverse-palindrome-p dna start i))))
+
+(define-problem revp (data stream)
+    *input-revp*
+    *output-revp*
+  (with-output-to-string (s)
+    (iterate
+      (with dna = (cdr (first (read-fasta-into-alist data))))
+      (for i :index-of-vector dna)
+      (when-let ((l (reverse-palindrome-length dna i)))
+        (format s "~D ~D~%" (1+ i) l)))))
+
+