在字符串中查找子串是一个常见问题。子串在字符串中可能是唯一的，比如特定的基因序列；也有可能有多个拷贝，比如基因组中的重复序列。这些重复序列可能相同，可能有微小区别。本题中重复子串完全相同，可以简单地通过 Python 的find()函数来查找，如果重复子串不完全相同并且符合某种模式，则可以用正则表达式模块re来处理。

给定： 两个 DNA 序列s和t（长度都不超过 1kb）。

需得： t在s中的所有位置。

示例数据

   

    

     

      

     
     

      

       GATATATGCATATACTT
      
     
    

     

      

     
     

      

       ATAT
      
     
   

示例结果

2 4 10

Python 实现

Finding_a_Motif_in_DNA.py

   

    

     

      

     
     

      

       import sys
      
     
    

     

      

     
     

      

       import re
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       def find_motif(s, t):
      
     
    

     

      

     
     

      

           ret = []
      
     
    

     

      

     
     

      

           pos = s.find(t)
      
     
    

     

      

     
     

      

           while pos != 
       -1:
      
     
    

     

      

     
     

      

               ret.
       append(pos+
       1)
      
     
    

     

      

     
     

      

               pos = s.find(t, pos+
       1)
      
     
    

     

      

     
     

      
    
       return 
       ' '.join([str(n) 
       for n in ret])
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       def test():
      
     
    

     

      

     
     

      
    
       return find_motif(
       'GATATATGCATATACTT', 
       'ATAT') == 
       '2 4 10'
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       if __name__ == 
       '__main__':
      
     
    

     

      

     
     

      
    
       if not test():
      
     
    

     

      

     
     

      
        
       print(
       "find_motif: Failed")
      
     
    

     

      

     
     

      

               sys.exit(
       1)
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

           with open(
       'rosalind_subs.txt') as fh:
      
     
    

     

      

     
     

      

               s = fh.readline().rstrip()
      
     
    

     

      

     
     

      

               t = fh.readline().rstrip()
      
     
    

     

      

     
     

      
        
       print(find_motif(s, t))
      
     
   

• 注意找到一个位置后，再次查找需要从下一个位置（pos+1）开始，以防止重复查找。

喜欢文章请点个“赞”吧！或者点击“在看”让更多朋友看到，点击“阅读原文”可以在知乎专栏上给我留言，博客地址：https://jianzuoyi.github.io