Changeset 55

Timestamp:

Apr 21, 2011, 4:04:44 PM (12 years ago)

Author:

robert@…

Message:

Adjusted artificial tag creation in order to avoid homopolymers (#37)

Location:

trunk

Files:

• grails-app/controllers/nl/tno/massSequencing/SampleController.groovy (modified) (2 diffs)
• grails-app/services/nl/tno/massSequencing/FastaService.groovy (modified) (2 diffs)
• test/unit/nl/tno/massSequencing/FastaServiceTests.groovy (modified) (1 diff)

trunk/grails-app/controllers/nl/tno/massSequencing/SampleController.groovy

@@ -99 +99 @@
                 tokens.each { token ->
                         sample = Sample.findBySampleToken( token );
-                        if( sample.study.canRead( session.user ) ) {
+                        if( sample?.study?.canRead( session.user ) ) {
                                 if( sample && sample.assaySamples )
                                         assaySamples += sample.assaySamples;
@@ -106 +106 @@
                 ids.each { id ->
                         sample = Sample.get( id );
-                        if( sample.study.canRead( session.user ) ) {
+                        if( sample?.study?.canRead( session.user ) ) {
                                 if( sample && sample.assaySamples )
                                         assaySamples += sample.assaySamples;

trunk/grails-app/services/nl/tno/massSequencing/FastaService.groovy

@@ -624 +624 @@
                 // The minimum number of characters used is 10, to ensure the correct working of the other
                 // programs.
-                int tagLength = Math.max( 10, Math.ceil( Math.log( assaySamples.size() ) / Math.log( 4 ) ) );
+                int tagLength = computeTagLength( assaySamples.size() )
                 int tagNumber = 0;
 
@@ -800 +800 @@
                 def numChars = chars.size();
 
-                if( tagNumber > numChars ** length )
+                // Determine whether the tagNumber is not too high
+                if( tagNumber > numChars * ( ( numChars - 1 ) ** ( length - 1 ) ) )
                         throw new Exception( "Given tag number (" + tagNumber + ") is too large for the specified length (" + length + ")")
 
                 String tag = "";
 
+                // Loop through all characters
                 for( def i = 0; i < length; i++ ) {
-                        int currentChar = tagNumber % numChars
-
-                        // Append the new character to the end of the tag, to ensure that the first part of the tag is
-                        // the most volatile. This way it is easy to find the end of the tag and the beginning of the real
-                        // sequence on first sight.
-                        tag = tag + chars[ currentChar ];
-
-                        tagNumber = Math.floor( tagNumber / numChars );
+                        def currentChars
+                        
+                        // Make sure the characters to choose from are different from
+                        // the previous character
+                        if( i == 0 )
+                                currentChars = chars;
+                        else
+                                currentChars = chars - tag[ 0 ]
+                                
+                        // Determine which character to append by taking the tagNumber modulo the number of characters
+                        int currentChar = tagNumber % currentChars.size()
+                        tag = currentChars[ currentChar ] + tag;
+                        
+                        tagNumber = Math.floor( tagNumber / currentChars.size() );
                 }
 
                 return tag;
+        }
+        
+        /**
+         * Computes the number of characters needed for a tag to be unique for the given number of samples
+         * @param numSamples    Number of samples to generate tags for
+         * @return                              Number of characters needed for a unique tag
+         */
+        public int computeTagLength( int numSamples ) {
+                // No homopolymers are allowed in the tag. For that reason we have
+                // 4 possibilities for the first character, and 3 for every next character
+                
+                // In order to allow enough characters, we take the 3log(numSamples), with a
+                // minimum of 10 
+                return Math.max( 10, Math.ceil( Math.log( numSamples ) / Math.log( 3 ) ) );
         }
 

trunk/test/unit/nl/tno/massSequencing/FastaServiceTests.groovy

@@ -21 +21 @@
     void testCreateTag() {
                 // Simple check for uniqueness on different lengths
-                for( int length = 1; length <= 5; length++ ) {
+                for( int length = 1; length <= 6; length++ ) {
                         println "Checking uniqueness on length " + length
                         
-                        int maxTags = 4 ** length;
+                        int maxTags = 4 * 3 ** ( length - 1);
                         List tags = []
                         for( int tagNum = 0; tagNum < maxTags; tagNum++ ) {
                                 String tag = fastaService.createTag( length, tagNum );
-                                assert tag.size() == length;
                                 tags << tag;
                         }